A - 床塗り

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

イカの高橋君は床を塗るのが大好きです。N \times N のマス目状に区切られた床を、友人の青木君と一緒に塗ることにしました。ただ塗るだけでは面白くないので、以下のようなゲームをしながら床を塗ることにしました。

  • 高橋君は赤のインクを使い、青木君は青のインクを使って床を塗る。
  • 塗り終わったら、赤のインクで塗られたマスと青のインクで塗られたマスの個数を数える。
  • 赤のマスが青のマスよりも多ければ高橋君の勝ち、青のマスが赤のマスよりも多ければ青木君の勝ち、そうでなければ引き分け。

高橋君と青木君は今床を塗り終わりましたが、勝敗を判定するのに手間取っています。2 人の代わりに勝敗を判定してください。

入力

入力はイカの形式で標準入力から与えられる。

N
S_1
S_2
:
S_N
  • 1 行目には、マス目の 1 辺の個数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
  • 2 行目からの N 行には、マス目の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、長さ N の文字列 S_i が与えられる。このうち j (1 ≦ j ≦ N) 文字目は、i 行目 j 列目のマスの情報を以下のように表す。
    • R の場合：このマスが赤のインクで塗られていることを表す。
    • B の場合：このマスが青のインクで塗られていることを表す。
    • . の場合：このマスがまだ塗られていないことを表す。

出力

高橋君の勝ちならば TAKAHASHI、青木君の勝ちならば AOKI、引き分けならば DRAW を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

4
R.RB
RR.B
BRBB
RRB.

出力例1

TAKAHASHI

赤が 7 マス、青が 6 マスなので赤の高橋君の勝ちです。

入力例2

2
..
..

出力例2

DRAW

いずれも 0 マスで同じなので引き分けです。

入力例3

3
BRB
RBR
BRB

出力例3

AOKI

赤が 4 マス、青が 5 マスなので青の青木君の勝ちです。

B - 直線塗り

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

イカの高橋君は床を塗るのが大好きです。床は N 個のマスが左右に 1 列に並んでいるような形をしています。左から i 個目のマスをマス i と呼ぶことにします。すでにいくつかのマスは塗られていますが、いくつかのマスは塗られていません。高橋君はインクを発射できる射程が R の銃を使って全てのマスを塗ろうとしています。高橋君は最初マス 1 にいます。そして、1 秒の間に以下のいずれか 1 つの行動が行えます。

  • 1 つ右のマスに移動する。すなわち、マス i からマス i+1 に移動する。ただし、マス N にいるときは行えない。
  • 銃を撃って床を塗る。マス i にいるときに銃を撃つと、マス i からマス i+R-1 までのマスを全て塗ることができる。ただし、i+R-1 が N より大きい場合は、マス i からマス N までのマスが塗られる。

高橋君が全てのマスを塗るためにかかる時間の最小値を求めてください。

入力

入力はイカの形式で標準入力から与えられる。

N R
S
  • 1 行目には、マス目の個数を表す整数 N (1 ≦ N ≦ 100) と銃の射程を表す整数 R (1 ≦ R ≦ N) が空白区切りで与えられる。
  • 2 行目には、長さ N の文字列 S が与えられる。このうち i (1 ≦ i ≦ N) 文字目は、マス i の情報を以下のように表す。
    • . の場合：このマスがまだ塗られていないことを表す。
    • o の場合：このマスがすでに塗られていることを表す。

出力

高橋君が全てのマスを塗るためにかかる時間の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

7 3
...o.o.

出力例1

6

銃を撃つ → 4 歩前進 → 銃を撃つ、という行動をとると時間が最小となります。

入力例2

8 4
...o.ooo

出力例2

3

銃を撃つ → 1 歩前進 → 銃を撃つ、という行動をとると時間が最小となります。

入力例3

4 4
oooo

出力例3

0

最初から全てのマスが塗られています。

C - Z塗り

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

イカの高橋君は床を塗るのが大好きです。床は N \times N のマス目状に区切られており、すでにいくつかのマスは塗られています。i 行目 j 列目のマスをマス (i,j) と呼ぶことにします。高橋君は特殊なインク発射装置を用いて床を塗ろうとしています。この装置を使うと、以下のように床を塗ることができます。

  • 任意の整数 r, c を入力して装置のボタンを押すと、「i = r かつ j ≦ c」または「i = r+1 かつ j ≧ c」を満たすようなすべてのマス (i,j) を塗ることができる。

高橋君は、全てのマスをこの装置で塗ろうと思っています。このとき、装置を使う必要のある回数の最小値を求めてください。

入力

入力はイカの形式で標準入力から与えられる。

N
S_1
S_2
:
S_N
  • 1 行目には、マス目の 1 辺の個数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
  • 2 行目からの N 行には、マス目の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、長さ N の文字列 S_i が与えられる。このうち j (1 ≦ j ≦ N) 文字目は、マス (i,j) の情報を以下のように表す。
    • . の場合：このマスがまだ塗られていないことを表す。
    • o の場合：このマスがすでに塗られていることを表す。

出力

装置を使う回数の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

7
...oooo
oo.....
ooooooo
ooooooo
.....oo
oooo...
ooooooo

出力例1

2

インク発射装置はこの入力のような形を綺麗に塗ることができます。

入力例2

4
.oo.
..oo
o..o
oo..

出力例2

3

入力例3

1
o

出力例3

0

はじめから全て塗られていることもあります。

D - カクカク塗り

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

イカの高橋君は床を塗るのが大好きです。床は N \times N のマス目状に区切られており、いくつか（0 個もありうる）のマスには障害物があります。高橋君はこの床を以下のルールで塗ろうと考えています。

  • 「今いるマスの床を塗って、上下左右いずれかの隣のマスに移動する」という行動を繰り返す。
  • 移動するたびに向きを 90 度回転する。すなわち、上または下に移動した直後には右または左に移動し、右または左に移動した直後には上または下に移動する。
  • すでに塗ったマスには移動しない。
  • マス目の外や障害物のあるマスには移動しない。

高橋君は、すでにどのマスからスタートするかを決めています。このとき、高橋君はうまく移動しながら床を塗ることで、障害物のない全てのマスを塗ることが可能でしょうか。ただし、スタート直後の移動方向や最後に塗るマスには特に指定はありません。また、最後のマスを塗った直後には移動する必要はありません。

入力

入力はイカの形式で標準入力から与えられる。

N
S_1
S_2
:
S_N

  • 1 行目には、マス目の 1 辺の個数を表す整数 N (2 ≦ N ≦ 400) が与えられる。

  • 2 行目からの N 行には、マス目の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、長さ N の文字列 S_i が与えられる。このうち j (1 ≦ j ≦ N) 文字目は、i 行目 j 列目のマスの情報を以下のように表す。

    • . の場合：このマスが床であることを表す。
    • # の場合：このマスに障害物があることを表す。
    • s の場合：このマスは床であり、高橋君がスタートしようと決めているマスであることを表す。

    ただし、これらの文字列の中には s がちょうど 1 つ存在すること、. が少なくとも 1 つ以上存在することが保証される。

部分点

この問題には部分点が設定されている。

  • N ≦ 50 を満たすデータセット 1 に正解した場合は、40 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 60 点が与えられる。

出力

全てのマスを塗ることが可能ならば POSSIBLE、そうでない場合は IMPOSSIBLE を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

5
#....
..s..
..#..
#....
##..#

出力例1

POSSIBLE

図のように移動しながら塗れば良いです。

figure

入力例2

5
s.###
..###
###..
#....
#..##

出力例2

IMPOSSIBLE

入力例3

3
..#
.s.
#..

出力例3

IMPOSSIBLE