1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include<stdio.h> int p[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 ans,cur; int x1,x2,y1,y2; int main() { void dfs(int ,int,int); int N; scanf("%d",&N); while(N--) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); p[x1][y1]=1; ans=100; dfs(x1,y1,0); printf("%d\n",ans); } return 0; } void dfs(int x1,int y1,int cur) { if(x1==x2 && y1==y2) { ans=cur>ans?ans:cur; } if(x1<0 || x1>8 || y1<0 || y1>8) return ; if(!p[x1+1][y1]){ p[x1][y1]=1; dfs(x1+1,y1,cur+1); p[x1][y1]=0; } if(!p[x1][y1+1]){ p[x1][y1]=1; dfs(x1,y1+1,cur+1); p[x1][y1]=0; } if(!p[x1-1][y1]){ p[x1][y1]=1; dfs(x1-1,y1,cur+1); p[x1][y1]=0; } if(!p[x1][y1-1]){ p[x1][y1]=1; dfs(x1,y1-1,cur+1); p[x1][y1]=0; } }
|