swe 4193 수영대회 결승전

- 다익스트라 쓰라는데, 어떻게 쓰는거지 확인해보기 - bfs 로 풀이함, 머무르는 것을 미리 시간을 더해줘서 큐에 넣어줌. - 오께이.  갈 수 있는 최소 시간을 계속해서 갱신해갑니다.

/*
15:00 수영대회 결승전

- 소용돌이 2초 유지, 1초 사라짐
- 머무르기 가능 -> bfs 에 경우 넣기

bfs 로 갈 수 있는 경우의 수를 해둡니다.
대기하는 시간을 3초로 합니다. 0,1 유지 그리고 2 때 이동 가능.
머무르기 가능한지 확인하기. 

- 소용돌이는

시간 
0 3 6
1 4 7
2 5 8

3으로 나머지가 0,과 1이면 소용돌이 있음
3으로 나눈 나머지가 2이면 소용돌이 없음.

-머무를 수 있다는 것에 대해서 체크하기.
들어가는 것, 들어가서 1초 대기, 들어가서 2초대기, 반복이므로, 오케이 넣을때 3개를 넣음
*/
 
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
#define SIZE 16
int map[SIZE][SIZE];
int minVal = 2123456789;
int startX, startY, endX, endY;
int N;
int sec;
struct point {
    int x, y, sec;
};
queue<point> que;
int visit[SIZE][SIZE];
int x, y, nx, ny;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
void problemIn() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    cin >> startX >> startY >> endX >> endY;
}
 
void init() {
    minVal = 2123456789;
    sec = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = 0;
            map[i][j] = 0;
        }
    }
}
 
void bfs() {
    while (!que.empty()) {
        x = que.front().x;
        y = que.front().y;
        sec = que.front().sec;
        que.pop();
 
        if (x == endX && y == endY) {
            minVal = min(minVal, sec);
        }
 
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] == 1) continue;
            if (sec + 1 <= visit[nx][ny] || visit[nx][ny] == 0) { // 갔던 길이라도 시간 단축이 된다면, 갈 수 있음
                // 0 이면 그냥 갈 수 있음
                if (map[nx][ny] == 0) {
                    visit[nx][ny] = sec+1; // 갈 수 있는 최소 시간 기록
                    que.push({ nx, ny, sec + 1 });
                    que.push({ nx, ny, sec + 2 });
                    que.push({ nx, ny, sec + 3 });
                }
                // 소용돌이가 있는데, 가라앉아 있으면,
                else if (map[nx][ny] == 2 && (sec % 3 == 2)) {
                    visit[nx][ny] = sec+1; // 갈 수 있는 최소 시간 기록
                    que.push({ nx, ny, sec + 1 });
                    que.push({ nx, ny, sec + 2 });
                    que.push({ nx, ny, sec + 3 });
                }
            }
        }
    }
 
    if (minVal == 2123456789) minVal = -1;
}
 
 
void solve() {
 
    visit[startX][startY] = 0;
    que.push({ startX, startY, 0 });
    que.push({ startX, startY, 1 });
    que.push({ startX, startY, 2 });
    bfs();
}
 
int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        problemIn();
        solve();
        cout << "#" << tc << " " << minVal << endl;
        init();
    }
    return 0;
}