[HackerRank] プログラミングコンテスト復習03 [Week of Code 24:Simplified Chess Engine]
3問目
急激に問題が難しくなった。
難易度がMediumとは思えない!とDisscussionsでも大騒ぎされていて頭抱える。
03: Simplified Chess Engine
概要
4×4の簡易版チェスをプレイする。
コマはクイーンQ
、ルークR
、ビショップB
、ナイトK
の4つ。
相手(黒)のクイーンを指定された手の間に取れば勝ち。
取れなければ負け。
入力として初期配置を与えられるので、手番内に勝てるYES
か負けるNO
かを出力する。
方針
スマートなやり方はさっぱり思いつかず。
各コマの動かせる範囲にクイーンがいたら勝てるのかと判断して、コマを全部動かした座標に、敵クイーンがいたら勝ちとした。
が、もちろん通らず......。
掲示板の討論を読んでいると、
例えば3ターン以内に勝ち負けを判断する場合、行動順序は
1.白 2.黒 3.白 と考えられるが、このとき黒がどういう動きをするのか、可能性が多くてさっぱりわからない
といった意見が散見していて余計にこんがらがる。
結果
Result: Wrong Answer
Score: 5.33pt
31テスト中5テストしか通らず。
考察
Mediumなのにさっぱりわからない。
全てのコマを動かして可能性を考えていくと、組合せ候補が爆発するため、賢い選択ではないようにおもえた。
コンテスト期間終了後にテストケースを見てもう一度挑戦したい。
コード(失敗作)
長くなったので、最後に
FIELD = ['A', 'B', 'C', 'D']
def moveN(now_pos):
col = FIELD.index(now_pos[0])
row = int(now_pos[1])
if_pos = [[col-2, row+1], [col-1, row+2], [col+1, row+2], [col+2, row+1],
[col+2, row-1], [col+1, row-2], [col-1, row-2], [col-2, row-1]]
new_pos = [[FIELD[i[0]], str(i[1])] for i in if_pos if -1<i[0]<4 and 0<i[1]<5]
return new_pos
def moveQ(now_pos):
col = FIELD.index(now_pos[0])
row = int(now_pos[1])
if_pos = []
for i in range(-3, 4):
if i != 0:
if_pos.append([col+i, row])
if_pos.append([col, row+i])
if_pos.append([col+i, row+i])
if_pos.append([col-i, row-i])
new_pos = [[FIELD[i[0]], str(i[1])] for i in if_pos if -1<i[0]<4 and 0<i[1]<5]
return new_pos
def moveR(now_pos):
col = FIELD.index(now_pos[0])
row = int(now_pos[1])
if_pos = []
for i in range(-3, 4):
if i != 0:
if_pos.append([col+i, row])
if_pos.append([col, row+i])
new_pos = [[FIELD[i[0]], str(i[1])] for i in if_pos if -1<i[0]<4 and 0<i[1]<5]
return new_pos
def moveB(now_pos):
col = FIELD.index(now_pos[0])
row = int(now_pos[1])
if_pos = []
for i in range(-3, 4):
if i != 0:
if_pos.append([col+i, row+i])
if_pos.append([col-i, row-i])
new_pos = [[FIELD[i[0]], str(i[1])] for i in if_pos if -1<i[0]<4 and 0<i[1]<5]
return new_pos
g = int(raw_input())
for i in range(g):
w, b, m = map(int, raw_input().split())
w_pos = [raw_input().split() for j in range(w)]
b_pos = [raw_input().split() for j in range(b)]
w_new_pos = []
for pos in w_pos:
if pos[0] == 'Q':
w_new_pos.extend(moveQ([pos[1], pos[2]]))
elif pos[0] == 'R':
w_new_pos.extend(moveR([pos[1], pos[2]]))
elif pos[0] == 'B':
w_new_pos.extend(moveB([pos[1], pos[2]]))
elif pos[0] == 'N':
w_new_pos.extend(moveN([pos[1], pos[2]]))
for pos in b_pos:
if pos[0] == 'Q':
if [pos[1], pos[2]] in w_new_pos:
print 'YES'
else:
print 'NO'