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


陣取りゲーム (paizaランク A 相当)

https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_camp_boss

JavaScriptで解いてみました。

メインの処理は、開始位置が２つの幅優先探索です。
方法は２通りあります。
1. queue(キュー)を２つ用意して、距離を管理しながら、幅優先探索をして、交互に陣地を広げる方法。
2. 幅優先探索では、距離が昇順でマス目に記録できるので、１つのキューへ、先頭に先攻の開始位置を、次に後攻の開始位置を入れ、幅優先探索をする方法。

最後に各プレイヤーの陣地を数えて、勝者を出力します。

個人的には、2の「1つのキューへ先攻後攻をまとめて入れて幅優先探索」が考えやすかったです。

***
# 1. キュー２つで、距離を管理しながら、幅優先探索

## C++の場合参考とPython3の場合参考の、幅優先探索中の、ターン判定の考え方

C++の場合参考とPython3の場合参考の解答例は、1.のqueue(キュー)を２つ用意して、距離を管理しながら、幅優先探索をして、交互に陣地を広げる方法です。

プレイヤーが２人なので、幅優先探索の中で、どちらのターンか判定する必要があります。

結論から言えば、現在地の距離をn(初期値0)、ABの合計ターン数をcount(初期値0、Aが偶数、Bが奇数)、Aが先攻の時,
|Aが先攻の時| A | B | A | B | A | B |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 0  | 1  | 1  | 2  | 2  |
| AB合計ターン数count/2  |  0  | 0.5  |1  | 1.5  |2  | 2.5  |
| 距離n += 1  | 1  | 1  | 2  | 2  | 3  | 3  |

となるので、相手のターンになる判定式は **`count/2 < n`** で表せます。
**先攻がBの場合** は、 **count=1から** です。表のcount/2=0.5からに相当するので、 **Aの距離nの初期値を1に** すれば、同じ条件式`count/2 < n`が使えます。

解答例(C++の場合参考とPython3の場合参考)では、Aの距離nの初期値は`aadd`とし、Aが先攻なら0、後攻なら1としています。

以上の結論を、以下の説明で詳しく解説します。

***

幅優先探索をシュミレーションして考えます。
キューの先頭から現在地の距離がnの場合を1つ取り出し、探索します。探索先の距離はn+=1で、これをキューに入れていきます。
同様に距離nを１つ１つ探索して、距離nの探索が全て終わったら、距離がn+=1の探索が始まる前に、相手のターンになるようにします。

よって、 **キューに入れている距離nが、n+=1に変わった時、相手のターンになります** 。

具体的に、現在地の距離をn(初期値0)、ABの合計ターン数をcount(初期値0、Aが偶数、Bが奇数)、Aを先攻とした時、nとcountとの間に何か関係式がないかを考えます。

Aがcount=0で距離n=0の探索をし、距離n=1となったら、Bのターンになるのでcount++します。
Bがcount=1で距離n=0の探索をし、距離n=1となったら、Aのターンになるのでcount++します。
Aがcount=2で距離n=1の探索をし、距離n=2となったら、Bのターンになるのでcount++します。

以下同様に探索をします。これを表にしてみます。

|Aが先攻の時| A | B | A | B | A | B |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 0  | 1  | 1  | 2  | 2  |
| AB合計ターン数count  | 0  | 1  |2  | 3  |4  | 5  |
| 距離n += 1  | 1  | 1  | 2  | 2  | 3  | 3  |

Aの距離nが0のとき、countそのまま0。距離1になるとき、count++してBのターン。
Bの距離nが0のとき、countそのまま1。距離1になるとき、count++してAのターン。
距離nがn+=1になるとき、count++したいですが、nとcountとの間に何か関係式がないでしょうか。つくれないでしょうか。

先攻Aの距離nと、countが揃ったら、考えやすそうです。
距離nが、countより大きくなって、距離n+=1となったらよさそうです。


:::note
`count/プレイヤー数`してみましょう。(本問題でプレイヤー数は2)
:::

`count/2`にして表にしてみます。
|Aが先攻の時| A | B | A | B | A | B |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 0  | 1  | 1  | 2  | 2  |
| AB合計ターン数count/2  |  0  | 0.5  |1  | 1.5  |2  | 2.5  |
| 距離n += 1  | 1  | 1  | 2  | 2  | 3  | 3  |

こうすると、先攻Aの距離nとcount/2が揃います。また、全てのプレイヤーの距離nが、距離n+=1となると、count/2より大きくなります。

(理由補足：なぜなら、先攻Aのターンから次のAのターンまで、count/2の差が1になり、全プレイヤーのcount/2はn+=(1未満)になるからです。(細かく言えば、count/2=(1/プレイヤー数)*(何番目のプレイヤーか - 1)です。プレイヤー数が増えても同じ発想でいけます))

よって、相手のターンになる条件は、距離nが、n+=(1未満)のconut/2より大きい、距離n+=1になった時、とできるので、 **`count/2 < n`** と書けます。

具体例を挙げると、
Aが先攻で距離n=0の探索が終わり、n=1になった時、count/2=0なので`count/2 < n` が成立します。
Bが後攻で距離n=0の探索が終わり、n=1になった時、count/2=0.5なので`count/2 < n` が成立します。



次に、Bが先攻の時を考えます。Bが先攻になるので、count初期値0をcount++して、count=1すなわちcount/2=0.5から考えます。

|Bが先攻の時| B | A |  B | A | B |A |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 0  | 1  | 1  | 2  | 2  |
| AB合計ターン数count/2  | 0.5  |1  | 1.5  |2  | 2.5  | 3 |
| 距離n += 1  | 1  | 1  | 2  | 2  | 3  | 3  |

しかし、これだと、Bが先攻で距離n=0の探索が終わり、n=1になった時、count/2=0.5なので`count/2 < n` は成立しますが、
Aのターンになって、距離n=0の探索が終わり、n=1になった時、count/2 = 1なので、count/2 = n となり、`count/2 < n` が成立しません。

これでは、相手のターンになる条件が共通で`count/2 < n`とはできません。

どうすればBが先攻でも共通で`count/2 < n`の条件が使えるか、考えます。

Bが先攻なので、初期値がcount+=1されて、count/2=0.5からになっています。Aが先攻の時の表を利用できないでしょうか。

|Aが先攻の時(再掲)| A | B | A | B | A | B |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 0  | 1  | 1  | 2  | 2  |
| AB合計ターン数count/2  |  0  | 0.5  |1  | 1.5  |2  | 2.5  |
| 距離n += 1  | 1  | 1  | 2  | 2  | 3  | 3  |

Bが先攻の時の表において、Aのターンで count/2 = 距離n+=1 となっているのを、count/2 < 距離n+=1 となるようにしたいです。すると、Aが先攻の時の表と同じ条件`count/2 < n`が使えるようになるのですが。。。


:::note
Aの距離nの初期値を+1する
:::
これを表にします。Aの距離nと距離n+=1が全て+1されます。
|Bが先攻の時(A初期値+1)| B | A |  B | A | B |A |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 1  | 1  | 2  | 2  | 3  |
| AB合計ターン数count/2  | 0.5  |1  | 1.5  |2  | 2.5  | 3 |
| 距離n += 1  | 1  | 2  | 2  | 3  | 3  | 4 |

Aが先攻の時(再掲)の表と比較すると、

|Aが先攻の時(再掲)| A | B | A | B | A | B |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 距離n  | 0  | 0  | 1  | 1  | 2  | 2  |
| AB合計ターン数count/2  |  0  | 0.5  |1  | 1.5  |2  | 2.5  |
| 距離n += 1  | 1  | 1  | 2  | 2  | 3  | 3  |

Aが先攻の時(再掲)のBの最初のターン以降と、Bが先攻の時(A初期値+1)の表は、全く同じになっています。
Bが先攻だとcount+=1されるので、Aが先攻の時の表のcount/2=0.5以降に相当します。
よって、Bが先攻の時の表のAの距離nの初期値を+１することで、Aが先攻の時(再掲)の表と、同じ表になります。

確認のために、Bが先攻の時(A初期値+1)の表を具体的に見てみると、
Bが先攻で距離n=0の探索が終わり、n=1になった時、count/2=0.5なので`count/2 < n` が成立します。
Aが後攻で距離n=1の探索が終わり、n=2になった時、count/2=1なので`count/2 < n` が成立します。
以下も同様に成立するので、先攻がAの場合と同じ`count/2 < n`の条件を使えます。

思考の流れを少し細かく書いたので、少々長くなりましたが、表のイメージが湧けば、本当は短くシンプルです。

まとめると、Aが先攻の時の表をイメージして、
キューに入れている距離nが、n+=1に変わった時、相手のターンになります(count++)。
相手のターンになるか判定する、nとcountの条件式を考えます。
countをプレイヤー数の２で割ると、先攻のAの距離nとcount/2が揃い、距離nが+=1されたとき、count/2より大きくなり、相手のターンになります。すなわち、条件式は`count/2 < n` と表せます。
先攻がBの場合は、count=1からなので、Aが先攻の表のcount/2=0.5以降に相当します。
同じ条件`count/2 < n` を使うには、Aの距離nの初期値を1にすればよいです。

解答例(C++の場合参考とPython3の場合参考)では、Aの距離nの初期値を`aadd`とし、Aが先攻なら0、後攻なら1としています。


## 解答例(C++の場合参考)
１のqueueを 2 つ用意して、距離を管理しながら交互に陣地を広げていく幅優先探索です。考え方は上記の通りです。

```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 N = lines[1];//先攻

//Aが先攻の時の初期値
let count = 0;//偶数(count%2=0)Aのターン、奇数(count%2=1)Bのターンとする。
let aadd = 0;//Aの距離の初期値(A先攻0,A後攻1,count/2<nをA先攻B先攻共通で使えるように)

let sums = [1,1];//[A,B]それぞれ取った陣地数。初期値は開始位置のみの１。
let out = false;//開始位置が決まってループ抜ける
let pass = true;//キューが空でパスする

//先攻がBの場合
if (N === "B") {
    count++;//Bのターンにする,count=1
    aadd++;//Aの距離の初期値を1に。
}
//マップ、盤面
let S = Array(H);
for (let i = 0; i < H; i++) {
    S[i] = lines[i + 2].split("");
}

//開始位置
let AB = [[], []];//２つのキューを用意。AはAB[0]、BはAB[1]
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (S[i][j] === "A") {
            AB[0].push([i, j, aadd]);//座標i,j　距離aadd
            S[i][j] = '*';//訪問済み
        }else if (S[i][j] === "B") {
            AB[1].push([i, j, 0]);//ABインデックス注意、座標i,j 距離0
            S[i][j] = '*';
        }
    }
}
//幅優先探索
while (AB[0].length > 0 || AB[1].length > 0) { //AかBのキューに未処理があればループ
    //キューが空ならパス
    if (AB[count%2].length === 0) {
        count++;//相手のターンへ
        pass = false;//パスするときfalseにする
    }
    //現在地の座標と距離
    let [x, y, n] = AB[count%2][0];
    //相手のターンになるか判定
    if (count/2 < n && pass) { //上記に詳しく書いた。
        count++;//相手のターンへ
        [x, y, n] = AB[count%2][0];//相手のx,y,nへ変更
    }
    //現在のターンのプレイヤーのキューの先頭を削除
    AB[count%2].shift();
    
    //陣取り
    for (let i = -1; i <= 1; i += 2){
        if(0 <= y+i && y+i < H && S[y+i][x] == '.'){
            S[y+i][x] = '*';//訪問済み
            sums[count%2]++;//陣地数を+1
            AB[count%2].push([y+i,x,n+1]);//キューへpush
        }
    
        if(0 <= x+i && x+i < W && S[y][x+i] == '.'){
            S[y][x+i] = '*';
            sums[count%2]++;
            AB[count%2].push([y,x+i,n+1]);
        }
    } 
    
}
//出力
console.log(sums[0], sums[1]);//陣地数
//勝者
if(sums[0] < sums[1]){
    console.log("B");
}else if(sums[0] == sums[1]){
    console.log("Draw");
}else{
    console.log("A");
}
```
## 解答例(Python3の場合参考)
１のqueueを 2 つ用意して、距離を管理しながら交互に陣地を広げていく幅優先探索です。
幅優先探索の中で、プレイヤー２人のうちどちらのターンかの判定は、C++の場合参考と同じです。
```javascript
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//方針：queueを 2 つ用意して、距離を管理しながら交互に陣地を広げていく
const [H, W] = lines[0].split(" ").map(Number);
//先攻後攻ab
let ab = lines[1];
const s = lines.slice(2,H + 2).map(elm => elm.split(""));

//ABどちらのターンか（偶数A奇数B）
let count = 0;
//Aの距離の初期値(A先攻0,A後攻1,count/2<nが使えるように)
let aadd = 0;
//A,Bが取った陣地数
let sums = [1, 1];
//パスフラグ
flag_pass = true;
//queueを 2 つ用意
ab_point = [[], []];

//もし先攻がBならば
if (ab == "B") { 
    count += 1; //Bのターンから
    aadd += 1;  //Aの距離は+1する(count/2<nが使えるように)
}
//A,Bの初期座標をab_pointへ
for (let y =0; y < H; y++) {
    for (let x = 0; x < W; x++) {
        if (s[y][x] == "A")
            ab_point[0].push([y, x, aadd]);
        if (s[y][x] == "B")
            ab_point[1].push([y, x, 0]);
    }        
}
//2人の操作によって盤面が変化しなくなったらゲームを終了
while (ab_point[0].length > 0 || ab_point[1].length > 0) {
    //ABどちらのターンか
    //queueが空ならパス
    if (ab_point[count % 2].length == 0) {
        count += 1;//相手ターンへ
        flag_pass = false;//パス
    }    
    //ターン開始    
    //現在座標[y,x]距離nをqueueから取り出す
    let [y, x, n] = ab_point[count % 2][0];
    //相手のターンになるか判定
    if (count / 2 < n && flag_pass) {
        count += 1;//相手のターンへ
        [y, x, n] = ab_point[count % 2][0];//相手のy,x,nへ
    } 
    //queueの先頭削除
    ab_point[count % 2].shift(); 
    //取った陣地に入れるabに、AとBどちらを入れるか、AとBどちらのターンか
    ab = count % 2 === 0 ? "A" :"B";
    
    //陣取り開始
    if (y > 0 && s[y - 1][x] === ".") {
        s[y - 1][x] = ab; //取った陣地にAかBを入れる
        sums[count % 2] += 1; //取った陣地数
        ab_point[count % 2].push([y - 1, x, n + 1]); //queueにpush,距離+1
    }    
    if (y < H - 1 && s[y + 1][x] === ".") {
        s[y + 1][x] = ab;
        sums[count % 2] += 1;
        ab_point[count % 2].push([y + 1, x, n + 1]);
    }
    if (x > 0 && s[y][x - 1] === ".") {
        s[y][x - 1] = ab;
        sums[count % 2] += 1;
        ab_point[count % 2].push([y, x - 1, n + 1]);
    }    
    if (x < W - 1 && s[y][x + 1] === ".") {
        s[y][x + 1] = ab;
        sums[count % 2] += 1;
        ab_point[count % 2].push([y, x + 1, n + 1]);
    }    
   
}//while

//取った陣地数
console.log(sums[0], sums[1]);
//勝者
if (sums[0] > sums[1]) {
    result = "A";
} else if (sums[0] === sums[1]) {
    result = "Draw";
} else {
    result = "B";
}    
console.log(result);
```
## 解答例(Ruby の場合参考)
キュー２つの幅優先探索です。キューはplayers[A]とplayers[B]です。
距離の管理は、探索前に、各キューにたまった、開始位置からの現在地の距離が等しい陣地の数`times`でします。これを今ターンの探索回数にします。探索中のキューに新しく陣地が入ってきても、今ターンでは探索されず、次ターンにまわされます。

例えば、探索前(陣取り前)に、キューに距離1の陣地が入っているとします。この時のキューの陣地数(times)を2とします。これを陣取り回数(forループ回数)にします。現在地距離1の陣地から、陣取りで距離2の陣地を取り、例えば3つ、キューに入れていきますが、これは今ターンでは処理されず、距離1の陣地2つだけが処理されます。距離1の陣地2つの処理が全て終わったら、キューには距離２の陣地が３つ残りますが、これは次の自分のターンで処理されます。


```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 n = lines[1];
const board = lines.slice(2).map(line => line.split(""));
let names = ['A', 'B'];//A,Bどちらのターンか
let players = {A: [[0, 0]], B: [[0, 0]]};//キュー２つ、初期値は仮に[0,0]とする。
//開始位置探索
board.forEach((row, y) => {
   row.forEach((val, x) => {
       if (val !== '#' && val !== ".") {
            let sym = val;//AかB
            players[sym][0] = [y, x];//キューの初期値に代入
            board[y][x] = sym;
       }
   }) ;
});
//移動量
const move = [[-1, 0], [0, 1], [1, 0], [0, -1]];//上右下左
//ターン初期値決定
let turn = names.indexOf(n);//先攻Aならturn=0から、先攻Bならturn=1から
//幅優先探索
while (players.A.length > 0 || players.B.length > 0) {
    const name = names[turn%2];//ABどっちのターンか
    //キューにたまった、現在地の距離が等しい陣地の数を、陣取りのforループの回数とする。
    const times = players[name].length;
    //現在地からの距離+1の探索先だけ陣取りする
    for (let i = 0; i < times; i++) {//AかBの、距離が等しい取った陣地分（times）繰り返す
        const [y, x] = players[name].shift();//キューから取り出し、現在地の座標とする。 
        //探索、陣取り
        move.forEach(v => {
            const [t, s] = [v[0], v[1]];
            let ny = y + t;
            let nx = x + s;
            
            if (0 <= ny && ny <= h - 1 && 0 <= nx && nx <= w - 1 &&
            board[ny][nx] === '.') {
                players[name].push([ny, nx]);//キューへ距離+1の陣地だけを入れる
                board[ny][nx] = name;//盤面にAかB記録
            }
        });
    }
    turn += 1;//相手のターンへ
}
//陣地数を数えて出力
let teri = {A: 0, B: 0};//テリトリー(陣地)数
board.forEach(row => {
    row.forEach(val => {
        if (val !== '#' && val !== '.') {
            teri[val] += 1;
            //jsはforEach内でcontinueは使えない
        }
    });
});
console.log(teri.A, teri.B);

//勝者出力
let ans;
let max = 0;
//陣地数(value)を比較して、多い方のプレイヤー(key)を出力
for (const [key, value] of Object.entries(teri)) {
    if (value > max) {
        max = value;
        ans = key;
    }    
}
console.log(ans);

```
# 2. １つのキューでまとめて幅優先探索
## 解答例(キュー１つ)
キュー１つで、先頭に先攻の開始位置、次に後攻の開始位置を入れて幅優先探索をします。
先攻の陣地の初期値を0とし、2,4,6...と偶数で陣地を取っていきます。
後攻の陣地の初期値を1とし、3,5,7...と奇数で陣地を取っていきます。
最後に、偶数の陣地・奇数の陣地を数え、先攻偶数・後攻奇数をA・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(num => Number(num));
const N = lines[1];//先攻
//盤面
const board = lines.slice(2).map(line => line.split(""));

//処理待ち配列キュー(queue)1つだけ、開始位置、先攻が先、後攻が後
let q = [];

//開始時プレイヤーのいるマス 
let out = [false, false];//各[A,B]プレイヤーマス決まったらtrueにして、breakする
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (board[i][j] === 'A') {
            //Aが先攻
            if (N === "A") {
                board[i][j] = 0;//先攻偶数とする
            } else {
                board[i][j] = 1;//後攻奇数とする
            }
            q.push([i, j]);
            //qの中、先攻が先
            if (out[1] === true) { //後攻Bが先にqに入ってたら
                q.reverse();//入れ替え
            }
            out[0] = true;//A決まり
        } else if (board[i][j] === 'B') {
            //Bが先攻
            if (N === "B") {
                board[i][j] = 0;
            } else {
                board[i][j] = 1;
            }
            q.push([i, j]);
            //qの中、先攻が先
            if (out[0] === true) { //後攻Aが先にqに入ってたら
                [q[0], q[1]] = [q[1], q[0]];//入れ替え
            }
            out[1] = true;//B決まり
        }
        if (out.every(v => v === true)) break;//[A,B]両方決まったらbreak;
    }
    if (out.every(v => v === true)) break;//[A,B]両方決まったらbreak;
}

//幅優先探索
while (q.length > 0) { //処理待ち配列queueが空になるまでループ

    //処理待ち配列queueの先頭から処理していく
    let [y,x] = q.shift();

    //陣取り  
    if (0 <= y - 1 && board[y - 1][x] === ".") {
        board[y - 1][x] = board[y][x] + 2;//盤面に偶数、奇数で記録
        q.push([y - 1,x]);
    }
    
    if (y + 1 < H && board[y + 1][x] === ".") {
        board[y + 1][x] = board[y][x] + 2;
        q.push([y + 1,x]);
    }
   
    if (0 <= x - 1 && board[y][x - 1] === ".") {
        board[y][x - 1] = board[y][x] + 2;
        q.push([y,x - 1]);
    }
    
    if (x + 1 < W && board[y][x + 1] === ".") {
        board[y][x + 1] = board[y][x] + 2;
        q.push([y,x + 1]);
    }
} //while

//偶数・奇数をカウント
let countEven = 0;//偶数の数
let countOdd  = 0;//奇数の数
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (board[i][j] % 2 === 0) { //偶数なら
            countEven += 1;
        } else if (board[i][j] % 2 === 1) { //奇数なら
            countOdd += 1;
        }
    }
}

//先攻偶数・後攻奇数をA・B置換
let [T_A, T_B] = [0, 0];//A・B陣地の数
if (N === "A") {　//先攻Aのとき
    T_A = countEven;
    T_B = countOdd;
} else {　//先攻Bのとき
    T_A = countOdd;
    T_B = countEven;
}

//出力
console.log(T_A, T_B);//陣地数
console.log(T_A > T_B ? "A" : "B");//勝者
```