HDU---2364 Escape【廣度優先搜尋】

Problem Description You find yourself trapped in a large rectangular room, made up of large square tiles; some are accessible, others are blocked by obstacles or walls. With a single step, you can move from one tile to another tile if it is horizontally or vertically adjacent (i.e. you cannot move diagonally).

To shake off any people following you, you do not want to move in a straight line. In fact, you want to take a turn at every opportunity, never moving in any single direction longer than strictly necessary. This means that if, for example, you enter a tile from the south, you will turn either left or right, leaving to the west or the east. Only if both directions are blocked, will you move on straight ahead. You never turn around and go back!

Given a map of the room and your starting location, figure out how long it will take you to escape (that is: reach the edge of the room).

Input On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

a line with two integers separated by a space, h and w (1 <= h, w <= 80), the height and width of the room;

then h lines, each containing w characters, describing the room. Each character is one of . (period; an accessible space), # (a blocked space) or @ (your starting location).

There will be exactly one @ character in each room description.

Output For each test case:

A line with an integer: the minimal number of steps necessary to reach the edge of the room, or -1 if no escape is possible.

Sample Input

2
9 13
#############
#@..........#
#####.#.#.#.#
#...........#
#.#.#.#.#.#.#
#.#.......#.#
#.#.#.#.#.#.#
#...........#
#####.#######
4 6
#.####
#.#.##
#...@#
######
        

Sample Output

31
-1
  



SOURCE:點選打開連結




題意：

    自己被困在迷宮中，要求可以前進，左轉，右轉。然而在遇到能轉彎的地方時必須轉彎，除非不能轉彎或者是轉彎才能直行，問至少經過多少步才能走出迷宮。




解析：

   略微變形的BFS，重點在于向左右方向移動。是以用vis數組來記錄所處的狀态。




代碼：


       
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int h,w;
int vis[85][85][4];    //用來記錄所處的位置及狀态
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
char str[85][85];

int bfs(const int x,const int y);

class node
{
public:
    int x;
    int y;
    int step;
    int face;
    node() {};
    node (int x,int y,int step,int face);
};

node::node(int x,int y,int step,int face)
{
    this->x=x;
    this->y=y;
    this->step=step;
    this->face=face;
}

int main(void)
{
    int t,x,y;
    cin>>t;
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        cin>>h>>w;
        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++)
            {
                cin>>str[i][j];
                if(str[i][j]=='@')
                {
                    x=i;
                    y=j;
                }
            }
        cout<<bfs(x,y)<<endl;
    }
    return 0;
}

int bfs(const int x,const int y)
{
    queue<node> q;
    node n(x,y,0,-1);   //在起始位置可以面向任意方向，是以face為-1
    int step,face,nx,ny;
    bool flag;   //用來判斷是否隻能直行
    vis[x][y][0]=1,vis[x][y][1]=1;   //在起始位置的四種狀态都為0，因為在行走的過程中不能經過起始狀态
    vis[x][y][2]=1,vis[x][y][3]=1;
    q.push(n);
    while(q.size())
    {
        flag=true;
        n=q.front();
        q.pop();
        if(n.x==0||n.x==h-1||n.y==0||n.y==w-1)
            return n.step;
        for(int i=0; i<4; i++)  //看看能不能轉彎
        {
            if(i%2!=n.face%2)  //隻能向左右方向走
            {
                nx=n.x+dx[i];
                ny=n.y+dy[i];
                step=n.step+1;
                face=i;
                if(nx>=0&&nx<h&&ny>=0&&ny<w&&str[nx][ny]=='.')
                {
                    flag=false;  //隻要左右方向能走就走，不管走沒走過
                    if(!vis[nx][ny][face])  //若沒有走過，将其加入隊列
                    {
                        if(nx==0||nx==h-1||ny==0||ny==w-1)
                            return step;
                        q.push(node(nx,ny,step,face));
                        vis[nx][ny][face]=1;
                    }
                }
            }
        }
        if(flag)  //若不能轉彎，則隻能直行
        {
            nx=n.x+dx[n.face];
            ny=n.y+dy[n.face];
            step=n.step+1;
            face=n.face;
            if(nx>=0&&nx<h&&ny>=0&&ny<w&&str[nx][ny]=='.'&&!vis[nx][ny][face])
            {
                if(nx==0||nx==h-1||ny==0||ny==w-1)
                    return step;
                q.push(node(nx,ny,step,face));
                vis[nx][ny][face]=1;
            }
        }
    }
    return -1;
}