読者です 読者をやめる 読者になる 読者になる

AtCoder Grand Contest 007 参加記

はい。 ox---- 1311(+17)
http://agc007.contest.atcoder.jp
Aのみ1完でした。B問題も手を出そうとしたんですが、日本語の問題文解釈とサンプルの手動計算が合わないので諦めた。

A - Shik and Stone

Python2

h,w=map(int,raw_input().split())
l=[]
#l=map(int,raw_input().split())
for i in range(h):
    l.append(list(raw_input()))
l[0][0]='.'
x=y=0
while 1:
    if x+1<w and l[y][x+1]=='#':
        x+=1
        l[y][x]='.'
    elif y+1<h and l[y+1][x]=='#':
        y+=1
        l[y][x]='.'
    else:
        break
for i in l:
    if '#' in i:
        print 'Impossible'
        exit()
print 'Possible'

移動をシミュしたけど実は左上から右下に移動するのに移動方向を右か下のみで移動というのは最短での移動と同等ということだった。移動をシミュしなくても'#'の個数がH+W-1かどうかで判定できたらしい。