在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 n列，每一个点可以用行号和列号来表示。
现在有个人站在第 1 行第 1 列，要走到第 行第 列。
只能向右或者向下走。
注意，如果行号和列数都是偶数，不能走入这一格中。
问有多少种方案。
输入
输入一行包含两个整数n,m 。
输出
输出一个整数，表示答案。
样例输入
3 4
样例输出
2
这边借鉴一个详细答案
#include<stdio.h> int count=0;//计数器 int valid(int row,int col,int n,int m)//判断当前位置是否可行 {if(row<n&&col<m)//保证下标不超界 if((row+1)%2!=0||(col+1)%2!=0)//行号和列不全为偶数 return 1; return 0; } void pass(int a[30][30],int row,int col,int n,int m) {int i,j; if(row==n-1&&col==m-1)//递归出口 {printf("第%d种走法:\n",++count); for(i=0;i<n;i++) {for(j=0;j<m;j++) printf("%d ",a[i][j]); printf("\n"); } printf("\n"); return;//结束此次递归 } //递归 if(valid(row+1,col,n,m))//向下 {a[row+1][col]=1; pass(a,row+1,col,n,m); a[row+1][col]=0;//回溯 } if(valid(row,col+1,n,m))//向右 {a[row][col+1]=1; pass(a,row,col+1,n,m); a[row][col+1]=0; } } int main() {int a[30][30]={0},n,m; a[0][0]=1;//初始化 scanf("%d%d",&n,&m); pass(a,0,0,n,m); if(count) printf("\n一共%d种解。\n",count); else printf("\n该方格阵无解。\n"); return 0; }
