hdu 1728 逃离迷宫 BFS加优先队列 DFS()

http://acm.hdu.edu.cn/showproblem.php?pid=1728

　　题意就是能否在规定的转弯次数内从起点走到终点。刚走时那步方向不算。

　　只会bfs(),但想到这题需要记录转弯次数，所以就想在建立的节点内部添加一个变量记录本次走的方向，然后和上次走的方向比较，不同就增加转弯次数。就这样，按照bfs一层一层扩展，为了将转弯次数少的先扩展，就想到采用优先队列。但是按照这种思路写出来的代码WA。

　　后来看到网上有人倒着记录最小转弯次数（blog），也是采用的优先队列。虽然不知道作者为什么要倒着来，但我尝试这用这种写法正着来，这样也能过。

　　参考代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 struct pos
 7 {
 8     int x, y,ori;
 9 };
10 pos dir[4] = { {1,0,1},{0,1,2},{-1,0,3},{0,-1,4} };//四个方向偏移数组，第三维是代表这个方向的。
11 struct Node
12 {
13     int x, y, cnt,dir;//cnt记录转弯次数
14     bool operator < (const Node& rhs)const { //由于要是cnt小的先出队列，所以重载<
15         return cnt > rhs.cnt;
16     }
17 };
18 priority_queue<Node> que;
19 int k, m, n, sx, sy, ex, ey;
20 bool flag;
21 int ans[105][105];//记录起点到能到达每个点时的最小转弯次数。
22 char map[105][105];
23 char s[105];
24 
25 bool in(int a, int b)
26 {
27     if (a >= 1 && a <= m&&b >= 1 && b <= n&&map[a][b] == '.') return true;
28     return false;
29 }
30 
31 void BFS()
32 {
33     while (!que.empty())
34     {
35         Node u, v;
36         u = que.top(); que.pop();
37 
38         if (u.cnt > k) continue;//超过最大转弯次数就不用管了。
39 
40         for (int i = 0; i < 4; i++)
41         {
42             v.x = u.x + dir[i].x;
43             v.y = u.y + dir[i].y;
44             v.cnt = u.cnt;
45             if (in(v.x, v.y))
46             {
47                 v.dir = dir[i].ori;//现在结点的方向是dir[i].ori
48                 if (u.dir != -1 && v.dir != u.dir) {
49                     v.cnt = u.cnt + 1;
50                 }
51                 if (ans[v.x][v.y] >=v.cnt) {//这里一定要有等号！
52                     ans[v.x][v.y] = v.cnt;
53                     que.push(v);
54                 }
55             }
56         }
57     }
58     if (ans[ex][ey] <= k) flag = true;
59 }
60 
61 int main()
62 {
63     int T;
64     scanf("%d", &T);
65     while (T--)
66     {
67         scanf("%d%d", &m, &n);
68         for (int i = 1; i <= m; i++)
69         {
70             scanf("%s", s);
71             for (int j = 0; j < n; j++)
72             {
73                 map[i][j + 1] = s[j];
74                 ans[i][j + 1] = 1e8;
75             }
76         }
77         scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
78         flag = false;
79         while (!que.empty()) que.pop();
80         Node node;
81         node.x = sx, node.y = sy;
82         node.dir = -1, node.cnt = 0;
83         que.push(node);
84         BFS();
85         if (flag) printf("yes
");
86         else printf("no
");
87     }
88 }

View Code 1

　　我就是按照原作者的思路照猫画虎的正着写了一下。其实之前网上有人说bfs()优先队列写会错，我很疑惑为什么不行，自己写的的确过不了。现在想想也许可能是因为我之前扩展结点后设置了访问数组，访问过的就不再访问了。而上面代码的想法是用ans数组更新答案。并且让能更新的结点入队列！这样可能能保证只要能更新答案一个结点可以走多次。就像有人说的以前都是求最小步数，结点最多走一次，但求最小转弯数时就不一样了。不知道想法对不对>_<.

　　网上大部分bfs()的办法都是到一个结点一直走到头。（blog1 blog2 ）这个想法的确很好。

　　参考代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 struct pos
 8 {
 9     int x, y;
10 };
11 pos dir[4] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
12 struct Node
13 {
14     int x, y, cnt;
15 };
16 queue<Node> que;
17 int vis[105][105];
18 char map[105][105];
19 char tmps[105];
20 int m, n, sx, sy, ex, ey, k;
21 
22 bool in(int a, int b)
23 {
24     if (a >= 1 && a <= m&&b >= 1 && b <= n&&map[a][b] == '.') return true;
25     return false;
26 }
27 
28 int bfs()
29 {
30     while (!que.empty())
31     {
32         Node u;
33         u = que.front(); que.pop();
34 
35         if (u.x == ex&&u.y == ey&&u.cnt <= k) return 1;
36 
37         Node v;
38         v.cnt = u.cnt + 1;////因为前面搜完了一个方向，就肯定会拐弯，所以要+1，也因此起点的cnt初始化为-1;  
39         for (int i = 0; i<4; i++)
40         {
41             v.x = u.x + dir[i].x;
42             v.y = u.y + dir[i].y;
43             while (in(v.x, v.y))
44             {
45                 if (!vis[v.x][v.y])
46                 {
47                     que.push(v);
48                     vis[v.x][v.y] = 1;
49                 }
50                 v.x += dir[i].x;
51                 v.y += dir[i].y;
52             }
53         }
54     }
55     return -1;
56 }
57 
58 int main()
59 {
60     int t;
61     scanf("%d", &t);
62     while (t--)
63     {
64         memset(vis, 0, sizeof(vis));
65         scanf("%d%d", &m, &n);
66         for (int i = 1; i <= m; i++)
67         {
68             scanf("%s", tmps);
69             for (int j = 0; j<n; j++)
70             {
71                 map[i][j + 1] = tmps[j];
72                 vis[i][j + 1] = 0;
73             }
74         }
75         scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
76 
77         while (!que.empty()) que.pop();
78         Node u;
79         u.x = sx, u.y = sy, u.cnt = -1;
80         vis[u.x][u.y] = 1;
81         que.push(u);
82 
83         int ans = -1;
84         ans = bfs();
85         if (ans >= 0)        printf("yes
");
86         else        printf("no
");
87     }
88     return 0;
89 }

View Code 2

　　最后就是dfs()解法。我本来看这道题没有深搜思路的，但觉得只要是搜索题，基本上两种方法都应该能做。就大概看了一下深搜解法。

　　参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct pos
{
    int x, y,ori;
};
pos dir[4] = { { 1,0,1 },{ 0,1,2 },{ -1,0,3 },{ 0,-1,4 } };//同bfs();
int ans[105][105];
char map[105][105];
char tmps[105];
bool flag;
int m, n, sx, sy, ex, ey, k;

bool in(int a, int b)
{
    if (a >= 1 && a <= m&&b >= 1 && b <= n&&map[a][b] == '.') return true;
    return false;
}

void dfs(int x, int y, int cnt, int direct)//搜索的坐标、转弯次数、方向
{
    if (x == ex&&y == ey&&cnt <= k) {
        flag = true;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int newx = x + dir[i].x;
        int newy = y + dir[i].y;
        if (in(newx, newy))
        {
            if (direct == -1 || direct == dir[i].ori)
            {
                ans[newx][newy] = cnt;
                dfs(newx, newy, cnt, dir[i].ori);
                if (flag) return;
            }
            else if(cnt<k&&ans[newx][newy]>cnt)
            {
                ans[newx][newy] = cnt + 1;
                dfs(newx, newy, cnt + 1, dir[i].ori);
                if (flag) return;
            }
        }
    }

}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &m, &n);
        for (int i = 1; i <= m; i++)
        {
            scanf("%s", tmps);
            for (int j = 0; j<n; j++)
            {
                map[i][j + 1] = tmps[j];
                ans[i][j + 1] = 1e8;
            }
        }
        scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
        flag = false;
        dfs(sx, sy, 0, -1);//开始时方向为设为-1
        if (flag) printf("yes
");
        else printf("no
");
    }
    return 0;
}

View Code 3