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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ATC 001 A - 深さ優先探索(2015/06/06)

AtcoderATC Python 競技プログラミング

回答

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")

こういうアルゴリズムがあっていても通らないことがあるので,C++とかJavaとかたまには書いておきたい.