paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 陣取りのターン数

陣取りのターン数 (paizaランク B 相当)

JavaScriptで解いてみました。幅優先探索をします。

現在地の距離がnやdistだとすると、探索先の距離はn+1やdist+1になります。現在地の距離または探索先の距離どちらかが、マスを '?' にするときの距離 l_i と一致するか決めて調べ、'?'にします。

解答例のうち、C++の場合参考とPython3の場合参考は、探索先が一致するかで、Rubyの場合参考は、現在地が一致するかで調べています。

また、キューに入れる情報も、各回答で異なります。
C++の場合参考とRubyの場合参考は、現在地の座標と、現在地の距離になるように、
Python3の場合参考は、現在地の座標と探索先の距離になるようにしています。

別の解き方では、盤面に距離を記録していき、最後に?や*に変換しました。

いろんな解答のしかたがあるので、しっくりくるものを参考にしてみてください。

解答例(C++の場合参考)

幅優先探索では、マス目の距離が必ず昇順に探索をするので、?にする距離lの配列Lを昇順ソートにすることで、計算量をO(HW) にできます。
Lの先頭のl_1から一致するか調べ、一致したら次のl_2、...と調べていきます。

LのインデックスをLnumとします。L[Lnum]の形で使います。

幅優先探索の中で、現在地の距離nの時、探索先の距離n+1がL[Lnum]に一致するか調べます。
L[Lnum]について、現在地の距離nまでのl_iは調べ済みなので、次のl_i+1を調べます。すなわち、L[Lnum] <= nのとき、Lnum++します。

キューに入れる情報は、現在地の座標と、現在地の距離になるようにしています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [H, W, N] = lines[0].split(" ").map(Number);

const S = [];//盤面
for (let i = 0; i < H; i++) {
    S[i] = lines[i + 1].split("");
}

const L = [];//距離lの配列
for (let i = 0; i < N; i++) {
    L[i] = Number(lines[i + H + 1]);
}
let Lnum = 0;//Lのインデックス、L[Lnum]の形で扱う。初期値は先頭の0とする。

//幅優先探索では、マス目の距離が必ず昇順で現れることを利用すると、 
//l をソートすることで O(HW) にできます。
L.sort((a, b) => a - b);

let q = []; //キュー
//開始位置探索
let out = false;//現在地発見ループbreak
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (S[i][j] === '*') {
            q.push([i, j, 0]);//開始位置のy座標,x座標,距離
            //Lに0が含まれているか(Lを昇順ソートしてあるので、Lnum=0を調べる)
            if (L[Lnum] === 0) {
                S[i][j] = '?';//0があれば?にする
            } else {
                S[i][j] = '*';//そうでなければ*
            }
            out = true;
            break;
        }
    }
    if (out) break;
}

//幅優先探索
while (q.length > 0) {
    const [y, x, n] = q.shift();//n(現在地の距離)
    /* これから探索先の距離n+1がL[num]と一致するか調べる。
    L[Lnum]が現在地の距離n以下だったら調べ済みなので、Lnum++する */
    if (L[Lnum] <= n) { 
        Lnum++;
    }
    //上下探索
    for (let i = -1; i <= 1; i += 2) {
        if (0 <= y + i && y + i < H && S[y + i][x] === ".") {
            //探索先の距離がL[Lnum]だったら
            if (n + 1 === L[Lnum]){
                S[y + i][x] = '?';
            }else{
                S[y + i][x] = '*';
            }
            
            q.push([y + i, x, n + 1]);//距離、次は+1
        }
    }
    //左右探索
    for (let i = -1; i <= 1; i += 2) {    
        if (0 <= x + i && x + i < W && S[y][x + i] === ".") {
            //探索先の距離がL[Lnum]だったら
            if (n + 1 === L[Lnum]){
                S[y][x + i] = '?';
            }else{
                S[y][x + i] = '*';
            }
            q.push([y, x + i, n + 1]);
        }
    }    
}
//盤面出力
for (let i = 0; i < H; i++) {
    console.log(S[i].join(""));
}

解答例(Python3の場合参考)

?にする距離lをquestion配列に入れ、探索先の距離nをquestion.includes(n)で?にするか調べます。
幅優先探索のキューpaintに入れる情報は、現在地の座標と探索先の距離にしています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [H, W, n] = lines[0].split(" ").map(Number);
const s = lines.slice(1, H + 1).map(line => line.split(""));
//まず最初に ? にするべき距離を question に入れます。
const question = lines.slice(H + 1).map(Number);
//このコードでは paint をキューとして使います。
let paint = [];

//次に開始位置 * の座標と距離を paint に追加します。
for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
        if (s[y][x] === "*") {
            if (question.includes(0)) {//距離0は？か
                s[y][x] = "?";
            }
            paint.push([y, x, 1]);//現在地と探索先の距離をキューに
        }    
    }
}

while (paint.length > 0) {
    let [y, x, n] = paint.shift();//探索先の距離n
    //探索先の盤面を埋めるのは"*"か"？"か
    let ast_or_que = "*";
    if (question.includes(n)) {
        ast_or_que = "?";
    }
    //上
    if (y > 0 && s[y - 1][x] === ".") {
        s[y - 1][x] = ast_or_que;//探索先を埋める
        paint.push([y - 1, x, n + 1]);
    }
    //下
    if (y < H - 1 && s[y + 1][x] === ".") {
        s[y + 1][x] = ast_or_que;
        paint.push([y + 1, x, n + 1]);
    }
    //左
    if (x > 0 && s[y][x - 1] === ".") {
        s[y][x - 1] = ast_or_que;
        paint.push([y, x - 1, n + 1]);
    }
    //右
    if (x < W - 1 && s[y][x + 1] === ".") {
        s[y][x + 1] = ast_or_que;
        paint.push([y, x + 1, n + 1]);
    }
}

//盤面出力
for (let y = 0; y < H; y++) {
    let ans = "";
    for (let x = 0; x < W; x++) {
        ans += s[y][x];
    }
    console.log(ans);
}

解答例(Rubyの場合参考)

?にする距離を配列lに入れ、現在地の距離distをl.includes(dist)で、?にするか調べます。
キューに入れる情報は、現在地の座標と、現在地の距離としています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [h, w, n] = lines[0].split(" ").map(Number);
//盤面
const board = lines.slice(1, h + 1).map(line => line.split(""));
//距離l
const l = lines.slice(h + 1).map(Number);
//最初の地点からの距離を配列 player に入れておくことで、距離の管理が楽にできます。
let player = [[0, 0, 0]];
//開始位置探索
board.forEach((row, y) => {
   row.forEach((val, x) => {
       if (val === '*') {
           player[0] = [y, x, 0];//開始位置の距離0
       }
   }) ;
});

const move = [[-1, 0], [0, 1], [1, 0], [0, -1]];//上右下左
//幅優先探索
while (player.length > 0) {
    let [y, x, dist] = player.shift();//distは現在地の距離
    //現在地は?か*か
    if (l.includes(dist)) {
        board[y][x] = '?';
    } else {
        board[y][x] = '*';
    }
    
    //移動
    move.forEach(v => {
        const [t, s] = [v[0], v[1]];
        ny = y + t;
        nx = x + s;
        if (0 <= ny && ny <= h - 1 && 0 <= nx && nx <= w - 1 &&
        board[ny][nx] === '.') {
            player.push([ny, nx, dist + 1]);    
        }
    });
}

console.log(board.map(row => row.join("")).join("\n"));

解答例(盤面に距離記録、最後に*や?に変換)

盤面に現在地からの距離の数値を記録していき、最後に距離lなら?、それ以外なら*に変換しています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//盤面の行数 H , 列数 W
const [H, W, N] = lines[0].split(" ").map(num => Number(num));
//盤面
const board = lines.slice(1,H + 1).map(line => line.split(""));
//答えを記録する盤面
const ans = lines.slice(1,H + 1).map(line => line.split(""));
//距離l
const L = lines.slice(H + 1).map(Number);

//処理待ち配列queueを設定
let queue = [];

//現在プレイヤーのいるマスは '*' 
let out = false;
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (board[i][j] === '*') {
            queue.push([i,j]);
            board[i][j] = 0;//初期位置を0に
            out = true;
            break;
        }
    }
    if (out) break;
}

//処理待ち配列queueが空になるまでループ
while (queue.length > 0) {
   
    //処理待ち配列queueの先頭から処理していく
    let [y,x] = queue.shift();

    //陣取り
   
    if (0 <= y - 1 && board[y - 1][x] === ".") {
        board[y - 1][x] = board[y][x] + 1;//盤面に距離を記録
        queue.push([y - 1,x]);
    }
    
    if (y + 1 < H && board[y + 1][x] === ".") {
        board[y + 1][x] = board[y][x] + 1;
        queue.push([y + 1,x]);
    }
   
    if (0 <= x - 1 && board[y][x - 1] === ".") {
        board[y][x - 1] = board[y][x] + 1;
        queue.push([y,x - 1]);
    }
    
    if (x + 1 < W && board[y][x + 1] === ".") {
        board[y][x + 1] = board[y][x] + 1;
        queue.push([y,x + 1]);
    }
    
} //while

//距離をlなら?それ以外なら*に変換
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        //盤面の距離がLに含まれるか
        if (L.includes(board[i][j])) {
            ans[i][j] = "?";
        //l以外の数値なら    
        } else if (!isNaN(board[i][j])) {
            ans[i][j] = "*"; 
        }
    }
}

//盤面を出力
console.log(ans.map(elm => elm.join("")).join("\n"));