神経衰弱（力試し編） (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

これは、B ランクの問題としてスキルチェックに出題されていた問題です。試しに解いてみましょう。
現時点では自力で正解することができない場合は、この問題を飛ばして次の問題に進んでください。
この問題の後に続く 4 つの問題に順番に取り組むことで、
この「神経衰弱」の問題を解くために必要な知識や考えた方を身につけることができます。

神経衰弱と呼ばれるトランプゲームのシミュレーションをしましょう。

簡単のため、トランプには数字のみ書かれているものと考えます。
また、トランプを縦 H 枚、横 W 枚の長方形の形に並べた状態でスタートすることにします。
ここで、H × W 枚のトランプには 1 〜 13 の数字のうちどれか1つが書かれています。
また、複数のトランプに同じ数字が書かれていることがあります。

プレイヤーが N 人おり、それぞれ 1 〜 N で番号付けられているものとします。
ゲームが始まると、1番の人から以下の手順でプレイしていきます。

・任意の2枚のトランプを捲る。
・捲った2枚のトランプに異なる数字が書かれていれば、次のプレイヤーの手番となる。そうでなければ、以下の操作を行う。
・ 2枚のトランプを取り除き、自分のものとする。
・トランプが全て取り除かれていれば、ゲームを終了する。
・手順の先頭に戻る。

ここで、N 番のプレイヤーの次のプレイヤーは 1 番のプレイヤーであるとします。

ゲームの初期状態におけるトランプの配置と、
ゲームが終わるまでに捲られたトランプに関する時系列順の記録が与えられます。
その記録を用いて、各プレイヤーが取り除いたトランプの枚数を求めてください。

例えば、入力例1は以下のようになります。

入力される値

入力は以下のフォーマットで与えられます。

H W N
t_{1,1} t_{1,2} ... t_{1,W}
t_{2,1} t_{2,2} ... t_{2,W}
...
t_{H,1} t_{H,2} ... t_{H,W}
L
a_1 b_1 A_1 B_1
a_2 b_2 A_2 B_2
...
a_L b_L A_L B_L

・ 1 行目に並べられたトランプの縦方向の枚数 H と横方向の枚数 W、プレイヤーの数 N が半角スペース区切りで与えられます。

・ 2 行目から H+1 行目までの H 行にかけて i (1 ≦ i ≦ H) 行 j (1 ≦ j ≦ W) 列に並べられたトランプに書かれた数字が半角スペース区切りで与えられます。

・ H+2 行目に記録の長さ L が与えられます。

・ H+3 行目から H+L+3 行目までの L 行にかけて、捲られたトランプの記録が時系列順で与えられます。これは、a_i 行 b_i 列のトランプと A_i 行 B_i 列のトランプが捲られたことを表します。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: i 行目には i 番目のプレイヤーが取り除いたトランプの枚数を出力してください。
出力は合計で N 行となります。各行の最後は改行し、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ H, W ≦ 13

・ H × W は52以下の2の倍数

・ 2 ≦ N ≦ 10

・ t_{i,j} は1,...,13のいずれか

・並べられたトランプの中に、同じ数字が書かれたトランプは2枚または4枚ある

・ 1 ≦ L ≦ 200

・ 1 ≦ a_i, A_i ≦ H

・ 1 ≦ b_i, B_i ≦ W

・ a_i 行 b_i 列および A_i 行 B_i 列のトランプは取り除かれていない

・ (a_i, b_i) ≠ (A_i, B_i)

入力例1: 2 2 2
1 2
2 1
4
1 1 2 1
1 1 1 2
1 1 2 2
1 2 2 1

出力例1: 4
0

入力例2: 2 5 3
5 8 8 6 3
3 6 3 3 5
8
1 4 2 2
1 3 2 1
2 4 2 3
1 3 1 5
2 5 1 1
2 1 1 2
1 5 2 1
1 2 1 3

出力例2: 6
2
2

問題一覧へ戻る