更新时间:2022-05-19 04:04:54
AC代码:
#include<stdio.h> #include<string.h> int a[9][9]={ {1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,1,0,1}, {1,0,0,1,1,0,0,0,1}, {1,0,1,0,1,1,0,1,1}, {1,0,0,0,0,1,0,0,1}, {1,1,0,1,0,1,0,0,1}, {1,1,0,1,0,1,0,0,1}, {1,1,0,1,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1}}; int b[9][9];//标记是否走过 int min; void Found(int x,int y,int endx,int endy,int sum) { if(sum>=64)//防止栈溢出 return; if(x==endx&&y==endy) { if(sum<min) min=sum; return; } if(x+1<9&&a[x+1][y]==0&&b[x+1][y]==0) { b[x+1][y]=1; Found(x+1,y,endx,endy,sum+1); b[x+1][y]=0; } if(x-1>=0&&a[x-1][y]==0&&b[x-1][y]==0) { b[x-1][y]=1; Found(x-1,y,endx,endy,sum+1); b[x-1][y]=0; } if(y+1<9&&a[x][y+1]==0&&b[x][y+1]==0) { b[x][y+1]=1; Found(x,y+1,endx,endy,sum+1); b[x][y+1]=0; } if(y-1>=0&&a[x][y-1]==0&&b[x][y-1]==0) { b[x][y-1]=1; Found(x,y-1,endx,endy,sum+1); b[x][y-1]=0; } } int main() { int i,j,n,m,x1,y1,x2,y2; scanf("%d",&n); while(n--) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); min=99999999; memset(b,0,sizeof(b)); Found(x1,y1,x2,y2,0); printf("%d\n",min); } return 0; }