uva 816 Abbott的复仇

题目链接：https://uva.onlinejudge.org/external/8/816.pdf

紫书：P165

题意：

有一个最多包含9*9个交叉点的迷宫。输入起点、离开起点时的朝向和终点，求一条最短路（多解时任意输出一个即可）。

分析：

BFS的结点对状态转移的影响的因素有哪些，那么这个结点就要包含哪些信息。

左右，和东南西北的转换。

首先规定东南西北的顺时针。根据左右转向求出下一个方位。

下一个节点的坐标是有当前位置，和下一个状态的方向决定。

图的构建也是根据对结点状态转移的影响建图的。 has_edge[r][c][dir][turn] ，当前状态(r,c,dir)向 turn 方向走是否有路。

复制代码#include <bits/stdc++.h> using namespace std; struct Node { int r,c,dir; Node (int r=0,int c=0,int dir = 0) : r(r),c(c),dir(dir) {} }; const int Maxn = 10; const char* dirs = "NESW"; const char* turns = "FLR"; int dir_id(char c) { return strchr(dirs,c) - dirs; } int turn_id(int c) { return strchr(turns,c) - turns; } const int dr[] = {-1,0,1,0}; const int dc[] = {0,1,0,-1}; Node walk(const Node& u,int turn) { int dir = u.dir; if(turn==1) dir = (dir - 1 + 4)%4; ///向左转 if(turn==2) dir = (dir+ 1)%4; ///向右转 return Node(u.r+dr[dir],u.c+dc[dir],dir); } bool inside(int r,int c) { if(r>=1&&r<=9&&c>=1&&c<=9) return true; else return false; } int has_edge[Maxn][Maxn][4][3]; int r0,c0,r1,c1,r2,c2,dir; bool read() { char s[99],s2[99]; if(scanf("%s%d%d%s%d%d",s,&r0,&c0,s2,&r2,&c2)!=6) return false; puts(s); dir = dir_id(s2[0]); r1 = r0 + dr[dir]; c1 = c0 + dc[dir]; memset(has_edge,0,sizeof(has_edge)); for(;;) { int r,c; scanf("%d",&r); if(r==0) break; scanf("%d",&c); while(scanf("%s",s)==1&&s[0]!='*') { for(int i=1; i<strlen(s); i++) { has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1; } } } return true; } int d[Maxn][Maxn][4]; Node p[Maxn][Maxn][4]; void print_ans (Node u) { vector<Node> nodes; for(;;) { nodes.push_back(u); if(d[u.r][u.c][u.dir]==0) break; u = p[u.r][u.c][u.dir]; } nodes.push_back(Node(r0,c0,dir)); int cnt = 0; for(int i=nodes.size()-1; i>=0; i--) { if(cnt%10==0) printf(" "); printf(" (%d,%d)",nodes[i].r,nodes[i].c); cnt++; if(cnt%10==0) printf("n"); } if(nodes.size()%10!=0) puts(""); } void bfs() { queue<Node> q; memset(d, -1, sizeof(d)); Node u(r1, c1, dir); d[u.r][u.c][u.dir] = 0; q.push(u); while(!q.empty()) { Node u = q.front(); q.pop(); if(u.r == r2 && u.c == c2) { print_ans(u); return; } for(int i = 0; i < 3; i++) { Node v = walk(u, i); if(has_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0) { d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1; p[v.r][v.c][v.dir] = u; q.push(v); } } } printf(" No Solution Possiblen"); } int main() { while(read()) { bfs(); } return 0; }

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 <bits/stdc++.h>
using namespace std;


struct Node
{
    int r,c,dir;
    Node (int r=0,int c=0,int dir = 0) : r(r),c(c),dir(dir) {}
};

const int Maxn = 10;
const char* dirs = "NESW";
const char* turns = "FLR";

int dir_id(char c)
{
    return strchr(dirs,c) - dirs;
}

int turn_id(int c)
{
    return strchr(turns,c) - turns;
}

const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

Node walk(const Node& u,int turn)
{
    int dir = u.dir;
    if(turn==1) dir = (dir - 1 + 4)%4;  ///向左转
    if(turn==2) dir = (dir+ 1)%4;       ///向右转
    return Node(u.r+dr[dir],u.c+dc[dir],dir);
}

bool inside(int r,int c)
{
    if(r>=1&&r<=9&&c>=1&&c<=9)
        return true;
    else return false;
}

int has_edge[Maxn][Maxn][4][3];
int r0,c0,r1,c1,r2,c2,dir;
bool read()
{
    char s[99],s2[99];
    if(scanf("%s%d%d%s%d%d",s,&r0,&c0,s2,&r2,&c2)!=6) return false;

    puts(s);
    dir = dir_id(s2[0]);
    r1 = r0 + dr[dir];
    c1 = c0 + dc[dir];

    memset(has_edge,0,sizeof(has_edge));
    for(;;)
    {
        int r,c;
        scanf("%d",&r);
        if(r==0) break;
        scanf("%d",&c);

        while(scanf("%s",s)==1&&s[0]!='*')
        {

            for(int i=1; i<strlen(s); i++)
            {
                has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = 1;
            }
        }

    }
    return true;

}

int d[Maxn][Maxn][4];
Node p[Maxn][Maxn][4];

void print_ans (Node u)
{
    vector<Node> nodes;
    for(;;)
    {
        nodes.push_back(u);
        if(d[u.r][u.c][u.dir]==0) break;
        u = p[u.r][u.c][u.dir];
    }
    nodes.push_back(Node(r0,c0,dir));

    int cnt = 0;
    for(int i=nodes.size()-1; i>=0; i--)
    {
        if(cnt%10==0) printf(" ");
        printf(" (%d,%d)",nodes[i].r,nodes[i].c);
        cnt++;
        if(cnt%10==0) printf("n");

    }
    if(nodes.size()%10!=0) puts("");
}

void bfs()
{
    queue<Node> q;
    memset(d, -1, sizeof(d));
    Node u(r1, c1, dir);
    d[u.r][u.c][u.dir] = 0;
    q.push(u);
    while(!q.empty())
    {
        Node u = q.front();
        q.pop();
        if(u.r == r2 && u.c == c2)
        {
            print_ans(u);
            return;
        }
        for(int i = 0; i < 3; i++)
        {
            Node v = walk(u, i);
            if(has_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0)
            {
                d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;
                p[v.r][v.c][v.dir] = u;
                q.push(v);
            }
        }
    }
    printf("  No Solution Possiblen");
}


int main()
{
    while(read())
    {
        bfs();
    }
    return 0;
}