LoginSignup
1
0

More than 1 year has passed since last update.

@ZampieriIsa

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

Last updated at Posted at 2022-09-25

陣取りのターン数 (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"));
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0