#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ll long long
using namespace std;
struct Pos{
int r;
int c;
int dir;
};
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, -1, 0, 1};
int M,N,ans=1e9;
int board[105][105];
int cost[4][105][105];
Pos start;
Pos dest;
int changeDir(int d)
{
if(d == 1) return 3;
if(d == 2) return 1;
if(d == 3) return 0;
return 2;
}
int diffDir(int cur, int hope)
{
if(cur == hope) return 0;
int cur_t = cur;
int leftCnt=0;
while(cur_t != hope){
cur_t--;
if(cur_t<0) cur_t +=4;
leftCnt++;
}
cur_t = cur;
int rightCnt=0;
while(cur_t != hope){
cur_t++;
if(cur_t>3) cur_t -=4;
rightCnt++;
}
return min(leftCnt, rightCnt);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> M >> N;
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
cin >> board[i][j];
cin >> start.r >> start.c >> start.dir;
cin >> dest.r >> dest.c >> dest.dir;
start.dir = changeDir(start.dir);
dest.dir = changeDir(dest.dir);
if(dest.r == start.r and dest.c == start.c){
cout << diffDir(dest.dir, start.dir);
return 0;
}
for(int z=0;z<4;z++)
for(int i=1;i<=M;i++)
fill(cost[z][i], cost[z][i]+N+1, 1e9);
queue<Pos> q;
q.push(start);
cost[start.dir][start.r][start.c] = 0;
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int d=0;d<4;d++)
{
int nr = cur.r;
int nc = cur.c;
for(int n=1;n<=3;n++)
{
nr += dr[d];
nc += dc[d];
int dval = diffDir(cur.dir, d);
int destval = 0;
if(nr == dest.r and nc == dest.c) destval = diffDir(d, dest.dir);
if(nr<1 or nc<1 or nr>M or nc>N) break;
if(board[nr][nc] == 1) break;
if(cost[d][nr][nc] <= cost[cur.dir][cur.r][cur.c] + dval + destval + 1) continue;
cost[d][nr][nc] = cost[cur.dir][cur.r][cur.c] + dval + destval + 1;
if(nr == dest.r and nc == dest.c) continue;
Pos t = {nr, nc, d};
q.push(t);
}
}
}
for(int d=0;d<4;d++)
ans=min(cost[d][dest.r][dest.c], ans);
cout << ans;
return 0;
}
- 핵심
board[dir][r][c]
를 사용해서 보드판의 입장
에서 어떤 방향을 가지고 있는지
에 따라 최소 값 갱신
cost를 비교
할 때 같은 cost
를 가지면 반드시 continue
로 넘겨줘야 한다
--> 그렇지 않으면 무조건 무한루프에 빠진다
출발지점
과 도착지점
이 같은 경우
예외처리
right / left 회전
중 최소 회전
을 찾는 diffDir
정의
- 느낀 점
프로그래머스
의 활주로 건설
이라는 문제로 처음 board 상태에 따른 3차원 배열
을 접했는데 종종 나오는 것 같다