UVA-816 BFS之从学会到放弃

发表于 | 分类于 | 阅读次数：

一道经典的BFS题目，细节很多，以后有机会再做一遍。

Abbott 的复仇

思路

相比较普通的BFS，这道题不同的是，每个交叉路口处，从哪个方向来，它是有确定的去的方向的。我们需要记录一下从东边来，直走行不行， 或者从东边来，左拐弯行不行。这就是代码中的hasedge。同时walk函数很简洁，记录了从哪边来到哪边去的最终的坐标变化。 记录我的几个错误点： BFS中忘了加Q.push. UVA中全局变量不能用y0，似乎以前师哥说过. print函数没有返回参数的话就是void,不能用int,这点我RE了无数次，看来还是得规范点. 再就是路径输出值得学习，用了p数组记录前驱，最终就是不断往前直到初始点。相比较递归打印路径，这个方法不会引起栈溢出，同时也很方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <math.h>
#include <sstream>
#include <queue>
#include <set>
#include <map>
using namespace std;

int x0,y0;
struct node{
    int x,y,dir;
};
char dir[] = "NESW";
char run[] = "FLR";          //F直走，L左拐弯，R右拐弯

int dir_id(char c)           //将方向和运动方向总结成一个整数
{
    return strchr(dir, c) - dir;
}

int run_id(char c)
{
    return strchr(run, c) - run;
}
int dir1[] = {-1,0,1,0};
int dir2[] = {0,1,0,-1};

node walk(node u, int turn)
{
    int dir = u.dir;
    if(turn == 1) dir = (dir + 3) % 4;
    if(turn == 2) dir = (dir + 1) % 4;
    return node{u.x + dir1[dir], u.y + dir2[dir], dir};
}

  node p[10][10][10];          //储存父亲节点的信息，用来输出路径
  int d[10][10][10];
  string s;
  int hasedge[10][10][5][5];
void print(node u)
{
    vector<node>V;
    while(1)
    {
        V.push_back(u);
        if(d[u.x][u.y][u.dir] == 0)  break;
        u = p[u.x][u.y][u.dir];
    }
    reverse(V.begin(), V.end());
    int cnt = 0;
    int sz = V.size();
    while(cnt != sz)
    {
        cout << ' ';
        for(int i = 0; i < min(10,sz); ++i)
        {
            printf(" (%d,%d)",V[cnt].x,V[cnt].y);
            cnt++;
            if(cnt == sz)
                break;
        }
        cout << '\n';
    }
}

void bfs(int x1,int y1,char c, int x2, int y2)
{
   memset(d , -1, sizeof(d));   //储存从源点到该点的最短距离.
   int num = dir_id(c);
   d[x0][y0][num] = 0;
   d[x1][y1][num] = 1;
   p[x1][y1][num] = node{x0,y0,num};
   queue<node>Q;
   node a;
   a.x = x1, a.y = y1, a.dir = num;
   Q.push(a);
   while(!Q.empty())
   {
       a = Q.front();
       Q.pop();
       if(a.x == x2 && a.y == y2)  { print(a); return ;}
       for(int i = 0; i < 3; ++i)        //是否可以进行0,1,2这三个转向
       {
           if(hasedge[a.x][a.y][a.dir][i])
           {
               node b = walk(a, i);
               if(d[b.x][b.y][b.dir] < 0)
               {
                   d[b.x][b.y][b.dir] = d[a.x][a.y][a.dir] + 1;
                   p[b.x][b.y][b.dir] = a;                  //设置d数组的原因在于记录第一次以这个方向到达这个点的踪迹，下一次再以相同的轨迹到达该点就不管用了
                   Q.push(b);
               }
           }
       }
   }
   cout << "  No Solution Possible" << '\n';
}

int main()
{
    string s1, s2;
    int a, b,x1,y1,x2,y2;
    char c;    //c储存起点的出发方向
    while(cin >> s)
    {
        if(s == "END") break;
        scanf("%d %d %c %d %d",&x1, &y1, &c, &x2, &y2);
        x0 = x1, y0 = y1;
        if(c == 'N') {x1--;}
        if(c == 'S') {x1++;}
        if(c == 'W') {y1--;}
        if(c == 'E') {y1++;}
        memset(hasedge, 0, sizeof(hasedge));
        while(getline(cin ,s1))
        {
            if(s1[0] == '0')
                break;
            int num1 = s1[0] - '0';
            int num2 = s1[2] - '0';
            stringstream ss(s1);
            while(ss >> s2)
            {
                if(isalpha(s2[0]))
                {
                    int num3 = dir_id(s2[0]);
                    for(int i = 1; i < s2.size(); ++i)
                    {
                        int num4 = run_id(s2[i]);
                        hasedge[num1][num2][num3][num4] = 1; //代表可以从num3方向转向num4方向
                    }
                }
            }
        }
        cout << s << '\n';
        bfs(x1,y1,c,x2,y2);
    }
}