두 동전

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 간단한 Queue 구현, 배열을 사용해도 무방
class Queue {
	constructor() {
		this.bucket = [];
		this.rear = -1;
		this.front = -1;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

// 다음에 탐색할 좌표가 보드를 벗어나는지 검사하는 함수
const checkOut = (n, m, x, y) => 0 <= x && x < n && 0 <= y && y < m;

const BFS = (n, m, arr, start, visited) => {
	const nx = [0, 0, -1, 1];
	const ny = [-1, 1, 0, 0];

	// 두 개의 Queue 선언
	let queue = new Queue();
	queue.enqueue(start);
	let nextQueue = new Queue();

	let depth = 1;
	while (!queue.isEmpty()) {
		const [[ax, ay], [bx, by]] = queue.dequeue();

		// 버튼을 누른 횟수가 10 을 초과한다면 탐색 종료
		if (depth > 10) break;

		for (let i = 0; i < 4; i++) {
			let [cx, cy] = [ax + nx[i], ay + ny[i]];
			let [dx, dy] = [bx + nx[i], by + ny[i]];

			// 떨어졌는지 검사
			let cnt = 0;
			if (!checkOut(n, m, cx, cy)) cnt += 1;
			if (!checkOut(n, m, dx, dy)) cnt += 1;

			// 두 개의 동전이 떨어진 경우
			if (cnt === 2) continue;
			// 한 개의 동전만 떨어진 경우
			if (cnt === 1) return depth;

			// 벽이라면 이동할 수 없음
			if (arr[cx][cy] === "#") [cx, cy] = [ax, ay];
			if (arr[dx][dy] === "#") [dx, dy] = [bx, by];

			// 방문한 곳은 다시 탐색하지 않음
			if (visited[cx][cy][dx][dy] === true) continue;

			// 방문 처리 및 다음 탐색을 위해 nextQueue 에 좌표 넣기
			visited[cx][cy][dx][dy] = true;
			nextQueue.enqueue([
				[cx, cy],
				[dx, dy],
			]);
		}

		// 버튼을 누른 횟수를 갱신하는 순간
		// nextQueue 에 queue 에 있는 좌표 넣기
		if (queue.isEmpty()) {
			queue = nextQueue;
			nextQueue = new Queue();
			depth += 1;
		}
	}

	// 두 동전을 떨어뜨릴 수 없거나, 버튼을 10 번 보다 많이 눌러야 하는 경우
	return -1;
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const arr = input.slice(1, n + 1).map((v) => v.split(""));

	// 두 동전의 위치 찾기
	let start = [];
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (arr[i][j] !== "o") continue;
			start.push([i, j]);
		}
	}

	// 4 차원 배열 생성
	const visited = Array.from({length: n}, () =>
		Array.from({length: m}, () =>
			Array.from({length: n}, () => Array(m).fill(false))
		)
	);

	// 시작 위치에 대한 방문 처리
	const [[ax, ay], [bx, by]] = start;
	visited[ax][ay][bx][by] = true;

	const depth = BFS(n, m, arr, start, visited);

	// 버튼을 누른 횟수 반환
	return depth;
};

console.log(solution(input));