题解 | #走方格的方案数#

#include <stdio.h>
#include <stdlib.h>

int cnt;
int **maze;

void DFS(int x,int y,int a,int b){      //  x:当前横坐标；y:当前纵坐标；a:目标横坐标；b:目标纵坐标
    if(x==a && y==b){       //  抵达终点，记数+1
        cnt++;
        return;
    }
    if (x<a && maze[x+1][y]==0) {      //  往右走
        
        maze[x+1][y]=1;       //  表示该路径已计算
        DFS(x+1,y,a,b);           
        maze[x+1][y]=0;         //  还原状态 
    }
    if(y<b && maze[x][y+1]==0){        //  往下走
        
        maze[x][y+1]=1;
        DFS(x,y+1,a,b);
        maze[x][y+1]=0;       //  还原状态
        
    }
        
}


int main() {
    int m,n;
    while (scanf("%d %d", &m, &n) != EOF) { 
        maze=(int**)calloc(n+1, sizeof(int*));
        for (int i=0; i<=n; i++) {
            maze[i]=(int*)calloc(m+1, sizeof(int));
        }
        cnt=0;
        DFS(0,0,n,m);
        printf("%d\n",cnt);
    }
    return 0;
}

DFS搜索经典