学步园

//DFS深度优先搜索，WA了5次就因为1个while后面的条件差了一个……教训啊！！！<br /> #include<iostream><br /> using namespace std;<br /> int map[22][22],possible,minstep,w,h,beginx,beginy;<br /> void dfs(int x,int y,int r,int di)//di是4个方向的编号 1:向上 2：向右 3：向下 4：向左<br /> {<br /> if(r > minstep) return;//剪枝，超过最少步数的深搜无效返回<br /> if(di == 1)<br /> {<br /> if(map[y-1][x] == -1||map[y-1][x] == 1) return;<br /> while(map[y-1][x] == 0||map[y-1][x] == 3)<br /> {<br /> if(map[y-1][x] == 3)<br /> {<br /> possible = 1;<br /> if(r < minstep)<br /> minstep = r;<br /> return;<br /> }<br /> y--;<br /> if(map[y-1][x] == -1) return;<br /> if(map[y-1][x] == 1)<br /> {<br /> map[y-1][x] = 0;<br /> break;<br /> }<br /> }<br /> dfs(x,y,r+1,1);<br /> dfs(x,y,r+1,2);<br /> dfs(x,y,r+1,3);<br /> dfs(x,y,r+1,4);<br /> map[y-1][x] = 1;//很关键！一定要改回来！注意DFS的出口处恢复被修改过的值<br /> }<br /> else if(di == 2)<br /> {<br /> if(map[y][x+1] == -1||map[y][x+1] == 1) return;<br /> while(map[y][x+1] == 0||map[y][x+1] == 3)<br /> {<br /> if(map[y][x+1] == 3)<br /> {<br /> possible = 1;<br /> if(r < minstep)<br /> minstep = r;<br /> return;<br /> }<br /> x++;<br /> if(map[y][x+1] == -1) return;<br /> if(map[y][x+1] == 1)<br /> {<br /> map[y][x+1] = 0;<br /> break;<br /> }<br /> }<br /> dfs(x,y,r+1,1);<br /> dfs(x,y,r+1,2);<br /> dfs(x,y,r+1,3);<br /> dfs(x,y,r+1,4);<br /> map[y][x+1] = 1;<br /> }<br /> else if(di == 3)<br /> {<br /> if(map[y+1][x] == -1||map[y+1][x] == 1) return;<br /> while(map[y+1][x] == 0||map[y+1][x] == 3)<br /> {<br /> if(map[y+1][x] == 3)<br /> {<br /> possible = 1;<br /> if(r < minstep)<br /> minstep = r;<br /> return;<br /> }<br /> y++;<br /> if(map[y+1][x] == -1) return;<br /> if(map[y+1][x] == 1)<br /> {<br /> map[y+1][x] = 0;<br /> break;<br /> }<br /> }<br /> dfs(x,y,r+1,1);<br /> dfs(x,y,r+1,2);<br /> dfs(x,y,r+1,3);<br /> dfs(x,y,r+1,4);<br /> map[y+1][x] = 1;<br /> }<br /> else if(di == 4)<br /> {<br /> if(map[y][x-1] == -1||map[y][x-1] == 1) return;<br /> while(map[y][x-1] == 0||map[y][x-1] == 3)<br /> {<br /> if(map[y][x-1] == 3)<br /> {<br /> possible = 1;<br /> if(r < minstep)<br /> minstep = r;<br /> return;<br /> }<br /> x--;<br /> if(map[y][x-1] == -1) return;<br /> if(map[y][x-1] == 1)<br /> {<br /> map[y][x-1] = 0;<br /> break;<br /> }<br /> }<br /> dfs(x,y,r+1,1);<br /> dfs(x,y,r+1,2);<br /> dfs(x,y,r+1,3);<br /> dfs(x,y,r+1,4);<br /> map[y][x-1] = 1;<br /> }<br /> }<br /> int main()<br /> {<br /> while(cin >> w >> h)<br /> {<br /> if(w == 0) break;<br /> memset(map,-1,sizeof(map));<br /> possible = 0;<br /> minstep = 10;<br /> for(int i = 1; i <= h;++i)<br /> for(int j = 1;j <= w;++j)<br /> {<br /> cin >> map[i][j];<br /> if(map[i][j] == 2)<br /> {<br /> map[i][j] = 0;<br /> beginx = j;<br /> beginy = i;<br /> }<br /> }<br /> //从起点开始向4个方向深搜<br /> dfs(beginx,beginy,1,1);<br /> dfs(beginx,beginy,1,2);<br /> dfs(beginx,beginy,1,3);<br /> dfs(beginx,beginy,1,4);</p> <p> if(possible)<br /> cout << minstep << endl;<br /> else cout << -1 << endl;<br /> }<br /> return 0;<br /> }