第十一届蓝桥第一场省赛题 走方格

07/10 14:47
阅读数 98

走方格

问题描述:
在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样。从上到下依次为第 1 至第 n 行,从左到右依次为第 1 至第 m 列,每一个点可以用行号和列号来表示。现在有个人站在第 1 行第 1 列,要走到第 n 行第 m 列。只能向右或者向下走。注意,如果行号和列号都是偶数,不能走入这一格中。问有多少种方案。
输入格式输入一行包含两个整数 n,m。
输出格式输出一个整数,表示答案。
样例输入1:
3 4
样例输出1
2
样例输入2:
6 6
样例输出2:
0
评测用例规模与约定对于所有评测用例,1 ≤ n ≤ 30, 1 ≤ m ≤ 30。











#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; 
} 

运行结果:
在这里插入图片描述
在这里插入图片描述
注意:题目要求输出结果只需解的个数即可,为了方便检查解是否正确,我多加了打印路径部分。


展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部