| ||||||||||
| 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