回答
Submission #421527 - AtCoder Typical Contest 001 | AtCoder
解説スライドが上がっているので,解放についてはそちらをご覧になったほうが良いと思います.
www.slideshare.net
Pythonで解く場合の注意
- とにかくTLEにハマる
処理速度の遅さに泣かされる結果となった.そのため,無駄な処理をしないように色々工夫した… つもりだった.
アルゴリズムはほとんど変えていないので,アルゴリズム自体はあっていたのだが… TLEでは意味が無いのだ!
- 対策
- (他の人のソースコードを読む) ← 非常に参考になりました
- sys.stdinを使って文字列を読み込む(多少の改善)
- 文字列の読み込みは内包表記で読み込む(多少の改善)
- すでに訪れたかどうかを確認するためのテーブルを準備しない(結構改善された)
- 訪れたマスを"#"にすることで解決
- dequeを使う(かなり改善された)
もちろんこれらを行わなくてもうまくやれば通るとは思いますが,私には無理でした\(^o^)/
多分dequeがいちばん効いてると思う.ほとんどコピペだったので,リファレンスを読んでおきたい.
8.3. collections — コンテナデータ型 — Python 3.3.6 ドキュメント
http://docs.python.jp/3.3/library/collections.html#collections.deque
import sys import collections H, W = map(int,sys.stdin.readline().split()) table = [list(row.rstrip("\n")) for row in sys.stdin.readlines()] deq = collections.deque() for i in range(H): for j in range(W): if table[i][j] == "s": deq.append((i, j)) break while len(deq) > 0: y, x = deq.popleft() if y < 0 or H <= y or x < 0 or W <= x or table[y][x] == "#": continue if table[y][x] == "g": print("Yes") break table[y][x] = "#" for nx, ny in [(x, y-1), (x, y+1), (x-1, y), (x+1, y)]: deq.append((ny, nx)) else: print("No")