蓝桥杯 剪格子

#include<stdio.h>
int dir[4][2]={0,1,0,-1,-1,0,1,0};
int vis[12][12],map[12][12];
int m,n,sum;
int check(int x,int y,int ans)
{
    if (x<1||y<1||x>n||y>m)
    return 0;
    if (vis[x][y])
    return 0;
    if (ans>sum/2)
        return 0;
    return 1;
}
int dfs(int x,int y,int ans)
{
    int i,p,q;
    if (ans==sum/2)
        return 1;
        for (i=0;i<4;i++)
    {
        p=x+dir[i][0];<span style="white-space:pre">				</span>//以（x,y）为原点，向周围进行搜索
        q=y+dir[i][1];
        if (check(p,q,ans))
          {
              vis[p][q]=1;
              int cnt=dfs(p,q,ans+map[p][q]);
              if (cnt)
                return cnt+1;
              vis[p][q]=0;<span style="white-space:pre">			</span>//退回
          }
    }
    return 0;
}
int main()
{
    int i,j;
    sum=0;
    scanf("%d%d",&m,&n);
    for (i=1;i<=n;i++)
       for (j=1;j<=m;j++)
          {
              scanf("%d",&map[i][j]);
              sum+=map[i][j];
          }
    if (sum%2)
    {
        printf("0\n");
        return 0;
    }
    vis[1][1]=0;
    printf("%d\n",dfs(1,1,map[1][1]));
    return 0;
}
           

一直不太会dfs，这个代码还是参考高手写的，一直感觉dfs就是三步走，判断函数，dfs函数，主函数，但就是细节掌握不准，欠练