陣取りゲーム (paizaランク A 相当)
JavaScriptで解いてみました。
メインの処理は、開始位置が２つの幅優先探索です。
方法は２通りあります。
- queue(キュー)を２つ用意して、距離を管理しながら、幅優先探索をして、交互に陣地を広げる方法。
- 幅優先探索では、距離が昇順でマス目に記録できるので、１つのキューへ、先頭に先攻の開始位置を、次に後攻の開始位置を入れ、幅優先探索をする方法。
最後に各プレイヤーの陣地を数えて、勝者を出力します。
個人的には、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となったらよさそうです。
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が使えるようになるのですが。。。
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 つ用意して、距離を管理しながら交互に陣地を広げていく幅優先探索です。考え方は上記の通りです。
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++の場合参考と同じです。
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つの処理が全て終わったら、キューには距離２の陣地が３つ残りますが、これは次の自分のターンで処理されます。
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に置換し、陣地数と勝者を出力します。
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");//勝者