題目鏈接：http://poj.org/problem?id=3009 真是不知道怎么回事兒，昨天晚上我寫了一晚上沒AC，今天重寫了一遍就果斷AC了。 這道題是使一個應(yīng)該說是拐了一點兒彎兒的dfs，就是當(dāng)且僅當(dāng)遇到障礙的時候停止，剩下的時間全都一直在走，而且需要判斷的是下一步是否是障礙，而不是當(dāng)前所在位置是否是障礙，而且，需要維護(hù)的是障礙會消失，所以需要用dfs來維持地圖的環(huán)境，搜索是逐點搜索的，就是用一個循環(huán)把不該停的地方跳過去就行了。。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 int w, h, map[25][25], sx, sy, ans;
9 bool ju;
10 const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
11 bool inMap(int x, int y)
12 {
13 return x >= 0 && x < h && y >= 0 && y < w;
14 }
15 void init()
16 {
17 for (int i = 0; i < h; i++)
18 for (int j = 0; j < w; j++)
19 if (map[i][j] == 2) {sx = i; sy = j;}
20 ans = (1 << 31) - 1; ju = 0;
21 }
22 void dfs(int x, int y, int step)
23 {
24 if (step > 10) return;
25 for (int i = 0; i < 4; i++)
26 {
27 if (map[x + dir[i][0]][y + dir[i][1]] == 1 || !inMap(x + dir[i][0], y + dir[i][1])) continue;
28 int xx = x, yy = y;
29 while (map[xx + dir[i][0]][yy + dir[i][1]] != 1)
30 {
31 xx += dir[i][0]; yy += dir[i][1];
32 if (!inMap(xx, yy)) break;
33 if (map[xx][yy] == 3)
34 {
35 ans = min(step, ans);
36 ju = 1;
37 return;
38 }
39 }
40 if (inMap(xx, yy))
41 {
42 map[xx + dir[i][0]][yy + dir[i][1]] = 0;
43 dfs(xx, yy, step + 1);
44 map[xx + dir[i][0]][yy + dir[i][1]] = 1;
45 }
46 }
47 }
48 int main()
49 {
50 while (~scanf("%d%d", &w, &h))
51 {
52 if (!w && !h) break;
53 memset(map, 0, sizeof(map));
54 for (int i = 0; i < h; i++)
55 for (int j = 0; j < w; j++) scanf("%d", &map[i][j]);
56 init();
57 dfs(sx, sy, 1);
58 if (ju) printf("%d\n", ans);
59 else printf("-1\n");
60 }
61 return 0;
62 }
63
|