[SWEA] 8382 방향전환

 

BFS를 이용해서 풀 수 있다

 

가로->세로 or 세로->가로 이렇게만 이동이 가능하다!

 

처음에 4방향 그대로 모두 check해줬더니 시간초과가 났다

근데 가로로 온다면 왼쪽에서 오든, 오른쪽에서 오든 똑같다

세로도 마찬가지다!

 

결국 가로 / 세로 나눠서 2방향으로 보면 시간안에 통과가 가능하다!

그렇게 하기 위해서는 하나는 0 하나는1로 생각하면 된다

4방향을 나누기 2만하면 0,1로 표현가능 하므로 그것만 바꿔주면 된다!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int dist[222][222][2];
bool check[222][222][2];
 
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool inner(int x,int y){
    return(0<=x && x<=200 && 0<=y && y<=200);
}
int main(){
    int t; scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        memset(check,0,sizeof(check));
        int x1,y1,x2,y2; scanf(" %d %d %d %d",&x1,&y1,&x2,&y2);
        x1+=100; y1+=100; x2+=100; y2+=100;
        queue<pair<int,pair<int,int>>> q;
        for(int i=0;i<4;i++) {
            q.push({i,{x1,y1}});
            check[x1][y1][i/2]=true;
            dist[x1][y1][i/2]=0;
        }
        while(!q.empty()){
            int prev = q.front().first;
            int x = q.front().second.first;
            int y = q.front().second.second;
            q.pop();
            if(prev<=1){
                for(int i=2;i<4;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(inner(nx,ny) && !check[nx][ny][i/2]){
                        check[nx][ny][i/2]=true;
                        dist[nx][ny][i/2]=dist[x][y][prev/2]+1;
                        q.push({i,{nx,ny}});
                    }
                }
            }else{
                for(int i=0;i<2;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(inner(nx,ny) && !check[nx][ny][i/2]){
                        check[nx][ny][i/2]=true;
                        dist[nx][ny][i/2] = dist[x][y][prev/2]+1;
                        q.push({i,{nx,ny}});
                    }
                }
            }
        }
        int ans = min(dist[x2][y2][0],dist[x2][y2][1]);
        printf("#%d %d\n",tc,ans);
    }
}