import java.util.*;

class Node {

private int pos1X;

private int pos1Y;

private int pos2X;

private int pos2Y;

private int distance;

public int getPos1X() {

return this.pos1X;

}

public int getPos1Y() {

return this.pos1Y;

}

public int getPos2X() {

return this.pos2X;

}

public int getPos2Y() {

return this.pos2Y;

}

public int getDistance() {

return this.distance;

}

public Node(int pos1X, int pos1Y, int pos2X, int pos2Y, int distance) {

this.pos1X = pos1X;

this.pos1Y = pos1Y;

this.pos2X = pos2X;

this.pos2Y = pos2Y;

this.distance = distance;

}

}

class Solution {

public ArrayList<Node> getNextPos(Node pos, int[][] board) {

// 반환 결과(이동 가능한 위치들)

ArrayList<Node> nextPos = new ArrayList<Node>();

// (상, 하, 좌, 우)로 이동하는 경우에 대해서 처리

int[] dx = {-1, 1, 0, 0};

int[] dy = {0, 0, -1, 1};

for (int i = 0; i < 4; i++) {

int pos1NextX = pos.getPos1X() + dx[i];

int pos1NextY = pos.getPos1Y() + dy[i];

int pos2NextX = pos.getPos2X() + dx[i];

int pos2NextY = pos.getPos2Y() + dy[i];

int distanceNext = pos.getDistance() + 1;

// 이동하고자 하는 두 칸이 모두 비어 있다면

if (board[pos1NextX][pos1NextY] == 0 && board[pos2NextX][pos2NextY] == 0) {

nextPos.add(new Node(pos1NextX, pos1NextY, pos2NextX, pos2NextY, distanceNext));

}

}

// 현재 로봇이 가로로 놓여 있는 경우

int[] hor = {-1, 1};

if (pos.getPos1X() == pos.getPos2X()) {

for (int i = 0; i < 2; i++) { // 위쪽으로 회전하거나, 아래쪽으로 회전

// 위쪽 혹은 아래쪽 두 칸이 모두 비어 있다면

if (board[pos.getPos1X() + hor[i]][pos.getPos1Y()] == 0 && board[pos.getPos2X() + hor[i]][pos.getPos2Y()] == 0) {

nextPos.add(new Node(pos.getPos1X(), pos.getPos1Y(), pos.getPos1X() + hor[i], pos.getPos1Y(), pos.getDistance() + 1));

nextPos.add(new Node(pos.getPos2X(), pos.getPos2Y(), pos.getPos2X() + hor[i], pos.getPos2Y(), pos.getDistance() + 1));

}

}

}

// 현재 로봇이 세로로 놓여 있는 경우

int[] ver = {-1, 1};

if (pos.getPos1Y() == pos.getPos2Y()) {

for (int i = 0; i < 2; i++) { // 왼쪽으로 회전하거나, 오른쪽으로 회전

// 왼쪽 혹은 오른쪽 두 칸이 모두 비어 있다면

if (board[pos.getPos1X()][pos.getPos1Y() + ver[i]] == 0 && board[pos.getPos2X()][pos.getPos2Y() + ver[i]] == 0) {

nextPos.add(new Node(pos.getPos1X(), pos.getPos1Y(), pos.getPos1X(), pos.getPos1Y() + ver[i], pos.getDistance() + 1));

nextPos.add(new Node(pos.getPos2X(), pos.getPos2Y(), pos.getPos2X(), pos.getPos2Y() + ver[i], pos.getDistance() + 1));

}

}

}

// 현재 위치에서 이동할 수 있는 위치를 반환

return nextPos;

}

public int solution(int[][] board) {

// 맵 외곽에 벽을 두는 형태로 맵 변형

int n = board.length;

int[][] newBoard = new int[n + 2][n + 2];

for (int i = 0; i < n + 2; i++) {

for (int j = 0; j < n + 2; j++) {

newBoard[i][j] = 1;

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

newBoard[i + 1][j + 1] = board[i][j];

}

}

// 너비 우선 탐색(BFS) 수행

Queue<Node> q = new LinkedList<>();

ArrayList<Node> visited = new ArrayList<>();

Node pos = new Node(1, 1, 1, 2, 0); // 시작 위치 설정

q.offer(pos); // 큐에 삽입한 뒤에

visited.add(pos); // 방문 처리

// 큐가 빌 때까지 반복

while (!q.isEmpty()) {

pos = q.poll();

// (n, n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환

if ((pos.getPos1X() == n && pos.getPos1Y() == n) || (pos.getPos2X() == n && pos.getPos2Y() == n)) {

return pos.getDistance();

}

// 현재 위치에서 이동할 수 있는 위치 확인

ArrayList<Node> nextPos = getNextPos(pos, newBoard);

for (int i = 0; i < nextPos.size(); i++) {

// 아직 방문하지 않은 위치라면 큐에 삽입하고 방문 처리

boolean check = true;

pos = nextPos.get(i);

for (int j = 0; j < visited.size(); j++) {

if (pos.getPos1X() == visited.get(j).getPos1X() && pos.getPos1Y() == visited.get(j).getPos1Y() && pos.getPos2X() == visited.get(j).getPos2X() && pos.getPos2Y() == visited.get(j).getPos2Y()) {

check = false;

break;

}

}

if (check) {

q.offer(pos);

visited.add(pos);

}

}

}

return 0;

}

}