[해커랭크] Castle on the Grid (C++)

문제 링크: www.hackerrank.com/challenges/castle-on-the-grid/problem

Castle on the Grid | HackerRank

1. 주의할 점

- 한쪽으로 기울이면 벽이 닿거나, 장애물에 닿을때까지 계속 움직일 수 있다.

- 벽이나 장애물에 닿아야만 공이 멈추는것이 아니다

 

2. 구현

- Check[][]배열을 통해 해당 지점에 도달하기 위해 최소 몇번 기울였는지 구한다

- 공의 시작점을 Queue에 넣는다

- 4방향 탐색을 하며 공을 진행시킨다. 이때, 공이 벽이나 장애물에 닿기 전까지 Check[][] 배열의 값을 갱신할 수 있다면 이동 가능한 위치를 Queue에 넣는다

- 목표지점에 도달할때까지 탐색한다

 

#include <bits/stdc++.h>

using namespace std;
struct info{
    int x,y;
};
info tmp;
char arr[100][100];
int sx,sy,tx,ty,num;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<string> split_string(string);
int check[101][101];
// Complete the minimumMoves function below.

int minimumMoves() {
    int result=0;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            check[i][j]=987654321;
        
    queue<info> q;
    tmp.x = sx;
    tmp.y = sy;
    q.push(tmp);
    check[sy][sx] = 0;
    while(!q.empty()){
        int cx = q.front().x;
        int cy = q.front().y;
        int cv = check[cy][cx];
        q.pop();
        if(cx==tx && cy==ty){
            result = cv;
            break;
        }
        for(int i=0;i<4;i++){
            int nx=cx,ny=cy;
            while(1){
                nx+=dx[i];
                ny+=dy[i];
                if(nx>=0 && ny>=0 && nx<num && ny<num && arr[ny][nx]=='.'){
                    if(check[ny][nx] > cv+1){
                        tmp.x=nx;
                        tmp.y=ny;
                        q.push(tmp);
                        check[ny][nx]=cv+1;
                    }
                    if(nx==tx && ny==ty){
                        result=cv+1;
                        break;
                    }
                }
                else{
                    nx-= dx[i];
                    ny-= dy[i];
                    break;
                }
            }
            if(result) break;
        }
        if(result) break;
    }
    return result;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    cin >> num;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    
    for (int i = 0; i < num; i++) {
        for(int j=0;j<num;j++)
            cin>>arr[i][j];
    }
    cin>>sy>>sx>>ty>>tx;
    
    int result = minimumMoves();

    fout << result << "\n";

    fout.close();

    return 0;
}