名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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

回答

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とかたまには書いておきたい.