Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
大牛帮我看下代码啊~!数据全过还是WA啊!!求救啊!!#include<iostream> using namespace std; int vis[22][22]; int route[22][22]; int possible; const int MAXN = 2147483647; int minstep; void dfs(int x,int y,int r,int map[][22],int di)//di是4个方向DFS的编号 { if(r > minstep) return; int temp[22][22]; memcpy(temp,map,22*22*sizeof(int)); if(di == 0) { dfs(x,y,r,temp,1); dfs(x,y,r,temp,2); dfs(x,y,r,temp,3); dfs(x,y,r,temp,4); } else if(di == 1) { if(temp[y+1][x] == -1||temp[y+1][x] == 1) return; route[y][x] = r; while(temp[y+1][x] == 0||temp[y+1][x] == 3) { if(temp[y+1][x] == 3) { possible = 1; if(r < route[y+1][x]) route[y+1][x] = minstep = r; return; } y++; if(temp[y+1][x] == -1) return; if(temp[y+1][x] == 1) { temp[y+1][x] = 0; break; } } dfs(x,y,r+1,temp,1); dfs(x,y,r+1,temp,2); dfs(x,y,r+1,temp,3); dfs(x,y,r+1,temp,4); } else if(di == 2) { if(temp[y][x+1] == -1||temp[y][x+1] == 1) return; route[y][x] = r; while(temp[y][x+1] == 0||temp[y][x+1] == 3) { if(temp[y][x+1] == 3) { possible = 1; if(r < route[y][x+1]) route[y][x+1] = minstep = r; return; } x++; if(temp[y][x+1] == -1) return; if(temp[y][x+1] == 1) { temp[y][x+1] = 0; break; } } dfs(x,y,r+1,temp,1); dfs(x,y,r+1,temp,2); dfs(x,y,r+1,temp,3); dfs(x,y,r+1,temp,4); } else if(di == 3) { if(temp[y-1][x] == -1||temp[y-1][x] == 1) return; route[y][x] = r; while(temp[y-1][x] == 0) { if(temp[y-1][x] == 3) { possible = 1; if(r < route[y-1][x]) route[y-1][x] = minstep = r; return; } y--; if(temp[y-1][x] == -1) return; if(temp[y-1][x] == 1) { temp[y-1][x] = 0; break; } } dfs(x,y,r+1,temp,1); dfs(x,y,r+1,temp,2); dfs(x,y,r+1,temp,3); dfs(x,y,r+1,temp,4); } else if(di == 4) { if(temp[y][x-1] == -1||temp[y][x-1] == 1) return; route[y][x] = r; while(temp[y][x-1] == 0||temp[y][x-1] == 3) { if(temp[y][x-1] == 3) { possible = 1; if(r < route[y][x-1]) route[y][x-1] = minstep = r; return; } x--; if(temp[y][x-1] == -1) return; if(temp[y][x-1] == 1) { temp[y][x-1] = 0; break; } } dfs(x,y,r+1,temp,1); dfs(x,y,r+1,temp,2); dfs(x,y,r+1,temp,3); dfs(x,y,r+1,temp,4); } } int main() { int map[22][22]; int w,h; int beginx,beginy,goalx,goaly; while(cin >> w >> h) { if(w == 0)break; memset(map,-1,sizeof(map)); memset(vis,0,sizeof(vis)); memset(route,0,sizeof(route)); possible = 0; minstep = 10; for(int i = 1; i <= h;++i) for(int j = 1;j <= w;++j) { cin >> map[i][j]; if(map[i][j] == 2) { beginx = j; beginy = i; } if(map[i][j] == 3) { goalx = j; goaly = i; } } route[goaly][goalx] = MAXN; route[beginy][beginx] = 1; map[beginy][beginx] = 0; dfs(beginx,beginy,1,map,0); if(possible) cout << minstep <<endl; else cout << -1 << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator