标签：广度优先搜索/BFS

题目内容

原文在文末，须认真阅读。

大意：给定一个迷宫，进入某个交叉点的方向不同，允许走出的方向也不同，求出从起点到终点的最短路并输出路径，如无解，输出 No Solution Possible

解题思路

思路就是一个 bfs，第一次到达终点时一定是最短路，遍历每个节点的时候存储上一个状态就可以逆推回去了。状态使用三元组 (r,c,dir) 表示。

但是此题需要注意很多细节：

• 起点只能往起点规定的方向走，不能任意出发
• IO 时的空格和换行问题
• 方向的转换
• (r_0,c_0,dir_0) 不能直接作为初始状态，需要先移动一格

代码的思路参照了紫书，p[r][c][dir] 存储此状态的上一个状态，d[r][c][dir] 存储到达此状态的最短路（相当于vis），has_edge[r][c][dir][turn] 存储当前状态能不能朝 turn 方向转弯。

思路很明了，注意细节即可，顺便吐槽 UVa 的毒瘤 IO，同时需要仔细阅读英文题面理解题面的意思。

#include <string>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

string maze_name;
int r0,c0,r1,c1,r2,c2;
char dir0;

struct node//bfs时的遍历状态
{
    int r,c,dir;//三元组存储
    node(){}
    node(int _r,int _c,int _dir)
    {
        r=_r,c=_c,dir=_dir;
    }
};

const char* dirs="NESW";
const char* turns="FLR";

inline int dir_id(char c)
{
    return strchr(dirs,c)-dirs;//将字母返回数字id
}

inline int turn_id(char c)
{
    return strchr(turns,c)-turns;//将字母返回数字id
}

inline bool chk(int r,int c)//防越界
{
    return 1<=r && r<=9 && 1<=c && c<=9;
}

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

bool has_edge[10][10][4][4];
node p[10][10][4];
int d[10][10][4];


inline node walk(const node &now,int turn)//返回某个状态转弯之后的状态
{
    int dir=now.dir;
    if(turn==1)//左转
        dir=(dir+3)%4;
    else if(turn==2)//右转
        dir=(dir+1)%4;
    return node(now.r+dr[dir],now.c+dc[dir],dir);//返回转完之后的状态
}

void print(node u)//打印路径
{
    vector<node> way;
    while(true)
    {
        way.push_back(u);//加入路径
        if(!d[u.r][u.c][u.dir])
            break;
        u=p[u.r][u.c][u.dir];//然后回溯上一个状态
    }
    way.push_back(node(r0,c0,dir_id(dir0)));
    int cnt=0;
    for(int i=way.size()-1;i>=0;i--)
    {
        if(cnt%10==0)
            cout<<' ';
        cout<<" ("<<way[i].r<<','<<way[i].c<<')';
        if(++cnt%10==0)
            cout<<endl;
    }
    if(way.size()%10)//注意io细节
        cout<<endl;
    return;
}

void bfs()
{
    cout<<maze_name<<endl;
    queue<node> q;
    memset(d,-1,sizeof d);
    memset(p,0,sizeof p);
    q.push(node(r1,c1,dir_id(dir0)));//先将初始状态加入
    d[r1][c1][dir_id(dir0)]=0;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.r==r2 && now.c==c2)//到达终点
        {
            print(now);
            return;
        }
        for(int i=0;i<3;i++)//枚举转弯的方向
        {
            node to=walk(now,i);//转个弯
            if(has_edge[now.r][now.c][now.dir][i] && chk(to.r,to.c) && d[to.r][to.c][to.dir]<0)//判断是否合法
            {
                d[to.r][to.c][to.dir]=d[now.r][now.c][now.dir]+1;
                p[to.r][to.c][to.dir]=now;
                q.push(to);
            }
        }
    }
    cout<<"  No Solution Possible"<<endl;//注意行首空格
}

bool read_maze()
{
    memset(has_edge,0,sizeof has_edge);
    cin>>maze_name;
    if(maze_name=="END")
        return false;
    cin>>r0>>c0>>dir0>>r2>>c2;
    r1=r0+dr[dir_id(dir0)];//注意(r0,c0)不能直接作为初始状态
    c1=c0+dc[dir_id(dir0)];
    int r,c;
    string tmp;
    while(true)//读入迷宫的点
    {
        cin>>r;
        if(!r)
            break;
        cin>>c>>tmp;
        while(tmp!="*")
        {
            int dir=dir_id(tmp[0]);
            for(int i=1;i<tmp.size();i++)
                has_edge[r][c][dir][turn_id(tmp[i])]=true;
            cin>>tmp;
        }
    }
    bfs();
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    while(read_maze());
    return 0;
}

题目原文

Description

The 1999 World Finals Contest included a problem based on a dice maze. At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last years problem statement. But we arehappy to report that Mr. Abbott has offered his expertise to this years contest with his original and unpublished walk-through arrow mazes.
As are most mazes,a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited.
These directions are always left, forward or right, or any combination of these.
Figure 1 illustrates a walk-through arrow maze. The intersections are identified as (row, column) pairs, with the upper left being (1,1). The Entrance intersection for Figure 1 is (3,1), and the Goal intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit(1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from(1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual(unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).
You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course.

Input

The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9.
The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.
All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is N,S,E or W to indicate in what direction of travel the sign would be seen. For example,’S’ indicates that this is the sign that is seen when travelling south.(This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be L,F or R indicating left, forward, and right, respectively.
The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word END on a single line by itself.

Output

For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase No Solution Possible. Maze names should start in column 1, and all other lines should start in column 3,i.e., indented two spaces. Solutions should be output as a list of intersections in the format(R,C) in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.