当前位置: 代码迷 >> 综合 >> 马的走法oj
  详细解决方案

马的走法oj

热度:24   发布时间:2024-01-14 22:35:51.0

 

Time Limit: 1000 ms  Memory Limit: 65536 KiB
Submit  Statistic
Problem Description
在一个4*5的棋盘上,马的初始位置坐标(纵 横)位置由键盘输入,求马能返回初始位置的所有不同走法的总数(马走过的位置不能重复,马走“日”字)。如果马的初始位置坐标超过棋盘的边界,则输出ERROR。例如初始位置为4 6,则输出ERROR。
Input
输入数据只有一行,有两个用空格分开的整数,表示马所在的初始位置坐标。首行首列位置编号为(1 1)。
Output
输出一行,只有一个整数,表示马能返回初始位置的所有不同走法的总数。

如果输入的马的初始位置超出棋盘边界,则输出ERROR。
Sample Input
2 2
Sample Output
4596
Hint
Source
#include<cstdio>  int sum,x,y;  
int vis[8][8]={0};  
// 地图状态 : 1为已走过,0为未走过   
int f[][2]={
  {-1,-2},{-1,2},{-2,1},{-2,-1},{1,2},{1,-2},{2,1},{2,-1}};  
// 马走的 8 个方向  int out(int x,int y){ // 判断是否超出地图   if(x<1 || x>4 || y<1 || y>5) return 1;  return 0;  
}  int dfs(int i,int j){ // 当前马的位置   for(int k=0;k<8;k++){ // 往8个方向走   int nx=i+f[k][0];  int ny=j+f[k][1];  if(out(nx,ny)) continue; //超出地图的不再走   if(nx==x && ny==y) sum++; // 能回到起点则 sum++   if(vis[nx][ny]) continue; // 曾走过的不再走   vis[nx][ny]=1; // 标记当前方向(nx,ny)为走过   dfs(nx,ny); // 走到(nx,ny)   vis[nx][ny]=0; // 这个方向所有的可能 已走完,(nx,ny)重新标记为未走(因为下一个方向可能会重复再走一次(nx,ny))   }  
}  int main(){  scanf("%d%d",&x,&y);  if(out(x,y)) puts("ERROR");  else{  sum=0;  vis[x][y]=1;  dfs(x,y);  printf("%d\n",sum);  }  return 0;  
}  


  相关解决方案