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

陣取りの結末 (paizaランク B 相当)

JavaScriptで解いてみました。

解答例

現在地を探索してから、幅優先探索をします。

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

const [H, W] = lines[0].split(" ").map(Number);
const S = lines.slice(1).map(line => line.split(""));
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]);//現在地をキューに
            out = true;
            break;
        }
    }
    if (out) break;
}
//幅優先探索
while (q.length > 0) { //キューが空になるまでループ
    let [ny, nx] = q.shift();//座標取り出し
    //上
    if (ny - 1 >= 0 && S[ny - 1][nx] === ".") {  //範囲内かつ未陣地
        S[ny - 1][nx] = '*';//陣地に
        q.push([ny - 1, nx]);//キューへ追加
    }
    //下
    if (ny + 1 < H && S[ny + 1][nx] === ".") {
        S[ny + 1][nx] = '*';
        q.push([ny + 1, nx]);
    }
    //左
    if (nx - 1 >= 0 && S[ny][nx - 1] === ".") {
        S[ny][nx - 1] = '*';
        q.push([ny, nx - 1]);
    }
    //右
    if (nx + 1 < W && S[ny][nx + 1] === ".") {
        S[ny][nx + 1] = '*';
        q.push([ny, nx + 1]);
    }
}

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

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

上下と左右の移動でforを使う。

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

const [H, W] = lines[0].split(" ").map(Number);
const S = lines.slice(1).map(line => line.split(""));

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]);
            out = true;
            break;
        }
    }
    if (out) break;
}

//幅優先探索
while (q.length > 0) { //空になるまでループ
    let [ny, nx] = q.shift();
    //上下
    for (let i = -1; i <= 1; i += 2) {
        if (ny - i >= 0 && ny + i < H && S[ny - i][nx] === ".") { //範囲内かつ未陣地
            S[ny - i][nx] = '*'; //陣地に
            q.push([ny - i, nx]);　//キューに追加
        }
    }
    //左右
    for (let i = -1; i <= 1; i += 2) {    
        if (nx - i >= 0 && nx + i < W && S[ny][nx - i] === ".") {
            S[ny][nx - i] = '*';
            q.push([ny, nx - i]);
        }
    }    
}

for (let i = 0; i < H; i++) {
    console.log(S[i].join(""));
}

解答例(Python3の場合参考)

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

const [H, W] = lines[0].split(" ").map(Number);
const S = lines.slice(1).map(line => line.split(""));
let q = [];//キュー
//現在地探索
for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
        if (S[y][x] === '*') {
            q.push([y, x]);//現在地をキューに追加
        }
    }
}
//幅優先探索
while (q.length > 0) { //キューが空になるまでループ
    let [ny, nx] = q.shift();//qから座標取り出し
    //上
    if (ny - 1 >= 0 && S[ny - 1][nx] === ".") {
        S[ny - 1][nx] = '*';//移動できるなら"*"に
        q.push([ny - 1, nx]);//キューに追加
    }
    //下
    if (ny + 1 < H && S[ny + 1][nx] === ".") {
        S[ny + 1][nx] = '*';
        q.push([ny + 1, nx]);
    }
    //左
    if (nx - 1 >= 0 && S[ny][nx - 1] === ".") {
        S[ny][nx - 1] = '*';
        q.push([ny, nx - 1]);
    }
    //右
    if (nx + 1 < W && S[ny][nx + 1] === ".") {
        S[ny][nx + 1] = '*';
        q.push([ny, nx + 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の場合参考)

const move = [[-1, 0], [0, 1], [1, 0], [0, -1]];で上下左右の確認をシンプルに。

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

const [H, W] = lines[0].split(" ").map(Number);
const board = lines.slice(1).map(line => line.split(""));

let player = [[0, 0]];
//現在地探索
board.forEach((row, y) => {
   row.forEach((val, x) => {
       if (val === '*') {
           player[0] = [y, x];
       }
   }) ;
});

const move = [[-1, 0], [0, 1], [1, 0], [0, -1]];//上右下左
//幅優先探索
while (q.length > 0) { //キューが空になるまでループ
    let [y, x] = q.shift();//キューから取り出す
    board[y][x] = '*';//現在地を陣地に
    //移動
    move.forEach(v => {
        const [t, s] = [v[0], v[1]];//tはyの変化量,sはxの変化量
        ny = y + t;
        nx = x + s;
        //盤面内かつ未陣地
        if (0 <= ny && ny <= H - 1 && 0 <= nx && nx <= W - 1 &&
        board[ny][nx] !== '#' && board[ny][nx] !== '*') {
            q.push([ny, nx]);//キューへ    
        }
    });
}

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

解答例

プレイヤーの座標を求めるのにbreakなし。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//盤面の行数 H , 列数 W
const [H,W] = lines[0].split(" ").map(num => Number(num));
//盤面
const board = lines.slice(1,H + 1).map(letter => letter.split(""));

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

//現在プレイヤーのいるマスは '*' 
//プレイヤーの座標[y,x]
let [y,x] = [];
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (board[i][j] === '*') {
            queue.push([i,j]);
        }
    }
}
//幅優先探索
//処理待ち配列queueが空になるまでループ
while (queue.length > 0) {
    
    //配列queueの先頭から処理していく
    let [y,x] = queue.shift();
   
    //陣取り
    //盤面内かつ未陣地
    if (0 <= y - 1 && board[y - 1][x] === ".") {
        board[y - 1][x] = '*';//陣地に
        queue.push([y - 1,x]);//キューへ
    }
    
    if (y + 1 < H && board[y + 1][x] === ".") {
        board[y + 1][x] = '*';
        queue.push([y + 1,x]);
    }
   
    if (0 <= 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] = '*';
        queue.push([y,x + 1]);
    }
    
} //while

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