[白俊]7562夜の移動-javascript
📌 質問する
https://www.acmicpc.net/problem/7562
📌 に答える
let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let tc = Number(input[0]);
let index = 1;
for (let i = 0; i < tc; i++) {
let board_size = Number(input[index]);
let board = new Array(board_size);
for (let j = 0; j < board.length; j++) {
board[j] = new Array(board_size).fill(0);
}
let start_x = Number(input[index + 1].split(" ")[0]);
let start_y = Number(input[index + 1].split(" ")[1]);
let end_x = Number(input[index + 2].split(" ")[0]);
let end_y = Number(input[index + 2].split(" ")[1]);
board[start_x][start_y] = 1;
function BFS() {
let L = 0;
let dx = [2, 2, -2, -2, 1, 1, -1, -1];
let dy = [1, -1, 1, -1, 2, -2, 2, -2];
let queue = [];
queue.push([start_x, start_y]);
while (queue.length) {
let len = queue.length;
for (let i = 0; i < len; i++) {
let v = queue.shift();
if (v[0] === end_x && v[1] === end_y) {
return L;
}
for (let i = 0; i < 8; i++) {
let nx = v[0] + dx[i];
let ny = v[1] + dy[i];
if (
nx >= 0 &&
nx < board_size &&
ny >= 0 &&
ny < board_size &&
board[nx][ny] === 0
) {
board[nx][ny] = 1;
queue.push([nx, ny]);
}
}
}
L++;
}
}
console.log(BFS());
index += 3;
}
✔アルゴリズム:BFS✔nightが移動できる方向は8種類あるので、dx,dyに8つの値を入れます
✔inputから受け取ったstart x、start y値をキューに入れBFSナビゲーションを開始
✔board[a][b]が1の場合、ナビゲーション中の現在のa、b座標がナビゲーション完了状態であることを示します
ナビゲーション->アクセス処理は、委員会[nx][ny]が0で10004 boardの範囲を超えない場合にのみ行い、queueにプッシュします.
移動回数を✔Lで計算し、queueからシフトしたときの到達点の座標と同じであれば、L(移動回数)を返します
✔難易度:白駿基準シルバー2
Reference
この問題について([白俊]7562夜の移動-javascript), 我々は、より多くの情報をここで見つけました https://velog.io/@ywc8851/백준-나이트의-이동-javascriptテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol