UVA314 Robot

BFS, Graph, Greedy

출처: UVA UVA314 Robot

SOL)
단순히 BFS로도 문제가 풀리며 Priority queue를 이용하여 해결할 수도 있다.
문제의 조건하에 최소의 비용으로 도착점까지 가기.
*(좌표 설정 확실히 문제마다 동서남북이 다름!)
[-] Collapse

#include<iostream>
#include<queue>
#include<stdio.h>
#include<string>
using namespace std;

int width, height;
int map[51][51][4];
int startX, startY;
int finishX, finishY;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
string direction;
//                     cost       direciton    location
queue< pair < int, pair < int, pair < int, int > > > > pq;

//0이면 갈 수 있고 1이면 갈 수 없다.
void init(){
    while (!pq.empty())
        pq.pop();
    for (int i = 0; i < 51; i++){
        for (int j = 0; j < 51; j++){
            for (int k = 0; k < 4; k++){
                map[i][j][k] = 0;
            }
        }
    }
}
void search(){
    while (1){
        if (pq.empty()){
            cout << "-1" << endl;
            return;
        }
        int cost = -pq.front().first;
        int di = pq.front().second.first;
        int y = pq.front().second.second.first;
        int x = pq.front().second.second.second;
        map[y][x][di] = 1;
        pq.pop();
        if (x == finishX && y == finishY){
            cout << cost << endl;
            return;
        }
        //방향 전환
        int newDi = (di + 1)%4;
        if (map[y][x][newDi] == 0){
            pq.push(make_pair(-1 * (cost + 1), make_pair((newDi) % 4, make_pair(y, x))));
            map[y][x][newDi] = 1;
        }
        newDi = di - 1;
        if (newDi < 0)
            newDi = di + 3;
        if (map[y][x][newDi] == 0){
            pq.push(make_pair(-1 * (cost + 1), make_pair((newDi) % 4, make_pair(y, x))));
            map[y][x][newDi] = 1;
        }

        //이동
        for (int i = 0; i < 3; i++){
            int nextX = x + dx[di] * (i + 1);
            int nextY = y + dy[di] * (i + 1);
            if (map[nextY][nextX][di] == 0 && nextX > 0 && nextY > 0 && nextX < width && nextY < height){
                pq.push(make_pair(-1 * (cost + 1), make_pair(di, make_pair(nextY, nextX))));
                map[nextY][nextX][di] = 1;
            }
            else if (map[nextY][nextX][di] == 2 && nextX > 0 && nextY > 0 && nextX < width && nextY < height)
                break;
        }
    }
}
int main(){
    freopen("input.txt", "r", stdin);
    int val = 0;
    while (1){
        cin >> height >> width;
        if (width == 0 && height == 0) break;
        init();
        for (int i = 0; i < height; i++){
            for (int j = 0; j < width; j++){
                cin >> val;
                if (val == 1){
                    for (int k = 0; k < 4; k++)
                        map[i][j][k] = map[i][j + 1][k] = map[i + 1][j][k] = map[i + 1][j + 1][k] = 2;
                }

            }
        }
        cin >> startY >> startX >> finishY >> finishX >> direction;
        int tempDi;
        if (direction == "east") tempDi = 2;
        else if (direction == "west") tempDi = 0;
        else if (direction == "south") tempDi = 3;
        else tempDi = 1;
        pq.push(make_pair(0, make_pair(tempDi, make_pair(startY, startX))));
        search();

    }
    return 0;
}