HDU 1180 기괴 한 계단 bfs

제목 링크
http://acm.hdu.edu.cn/showproblem.php?pid=1180
제목 분석:
이것 은 우리 에 게 가장 짧 은 시간 을 찾 으 라 는 것 이다.일반적으로 이런 문제 에 부 딪 히 면 모두 BFS 로 해 야 한다.
 
이 지 도 는 바 뀔 수 있 기 때문에 우 리 는 그의 서로 다른 시간의 지 도 를 저장 한 다음 에 시간 에 따라 어떤 지 도 를 사용 해 야 하 는 지 확인 해 야 한다.
우선 스 택 노드 에 들 어 가 는 데 필요 한 속성 을 확인 해 야 합 니 다.
좌표 x,y
현재 상태 s 는 현재 맵 을 사용 할 지 확인 하 는 데 사 용 됩 니 다.
타임 타임
그 밖 에 우 리 는 배열 vis[지도][x][y]를 표시 해 야 한다.
이 점 이 창고 에 들 어 갔 는 지 아 닌 지 를 판단 하 는 데 쓰 인 다.그렇지 않 으 면 창고 가 터 질 것 이다.
 
 

#include <iostream>

#include <vector>

#include <stack>

#include <cstdlib>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <string>

#include <queue>

using namespace std;

#define maxn 120

#define INF 0xffffff

struct Point

{

    int x, y;

    int time;

    int s;

}Ps, Pe;

int dir[5][2] = { {0,0},{1,0},{-1,0},{0,1},{0,-1} };

char maps[2][maxn][maxn];

bool vis[2][maxn][maxn];

int m, n;



bool OK(Point P)

{

    return P.x >= 0 && P.x < m&& P.y >= 0 && P.y < n  && maps[P.s][P.x][P.y] != '*' ;

}



int BFS()

{

    Point Pn, P;

    queue<Point> Q;

    Q.push(Ps);

    vis[Ps.s][Ps.x][Ps.y] = true;

    while( !Q.empty() )

    {

        P = Q.front();

        Q.pop();

        if( P.x == Pe.x && P.y == Pe.y )

            return P.time;

        

        for(int i=0; i<5; i++)

        {

            Pn = P;

            Pn.x = P.x + dir[i][0];

            Pn.y = P.y + dir[i][1];

            Pn.s ^= 1;

            Pn.time ++;

            if( OK(Pn) && maps[Pn.s][Pn.x][Pn.y] == '.' && !vis[Pn.s][Pn.x][Pn.y])

            {

                

                vis[Pn.s][Pn.x][Pn.y] = true;

                Q.push(Pn);

            }

            else if( (maps[Pn.s^1][Pn.x][Pn.y] == '|' && i <= 2 && i >= 1 ) || (maps[Pn.s^1][Pn.x][Pn.y] == '-' && i >= 3) )

            {

                

                Pn.x += dir[i][0];

                Pn.y += dir[i][1];

                

                if( OK(Pn)  && !vis[Pn.s][Pn.x][Pn.y])

                {

                    Q.push(Pn);

                    vis[Pn.s][Pn.x][Pn.y] = true;

                }

            }

            

        }

    }

    return -1;

}



int main()

{

    while(cin >> m >> n)

    {

        memset(vis,0,sizeof(vis));

        for(int i=0; i <m; i++)

        {

            cin >> maps[0][i];

            for(int j=0; j<n; j++)

            {

                if(maps[0][i][j] == 'S')

                    Ps.x = i, Ps.y = j, Ps.time = 0, maps[0][i][j] = '.', Ps.s = 0;

                if(maps[0][i][j] == 'T')

                    Pe.x = i, Pe.y = j,  maps[0][i][j] = '.';

                

                if(maps[0][i][j] == '|')

                    maps[1][i][j] = '-';

                else if(maps[0][i][j] == '-')

                    maps[1][i][j] = '|';

                else

                    maps[1][i][j] = maps[0][i][j];

            }

        }

        int ans = BFS();

        cout << ans << endl;

    }

    return 0;

}