Submission #11419127
Source Code Expand
# -*- coding: utf-8 -*- # A - 深さ優先探索 """ 高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、 高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。 高君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。 """ ''' 10 10 s......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. g.#.#.#.#. #.#.#.#.#. ###.#.#.#. #.....#... ''' import sys # 再起回数上限変更 sys.setrecursionlimit(20000) class Dbs(object): def __init__(self, H, W, data, sh, sw, gh, gw): self.H = H self.W = W self.data = data self.visited = [[False] * W for _ in range(H)] self.sh = sh self.sw = sw self.gh = gh self.gw = gw def search(self, r, c): """ row,colでサーチ試す,行けたら visited = Trueに設定 """ if (r < 0) | (r > H - 1) | (c < 0) | (c > W - 1): return if self.data[r][c] == '#': return if self.visited[r][c]: return self.visited[r][c] = True if (r, c) == (gh, gw): print('Yes') sys.exit() self.search(r + 1, c) self.search(r - 1, c) self.search(r, c + 1) self.search(r, c - 1) H, W = map(int, input().split()) mat = [[0] * W for _ in range(H)] # matとstart, goal のindex for ind_h in range(H): temp = input() for ind_w in range(W): mat[ind_h][ind_w] = temp[ind_w] if temp[ind_w] == 's': sh, sw = ind_h, ind_w elif temp[ind_w] == 'g': gh, gw = ind_h, ind_w # print(mat) dbs = Dbs(H, W, mat, sh, sw, gh, gw) dbs.search(sh, sw) print('No')
Submission Info
Submission Time | |
---|---|
Task | A - 深さ優先探索 |
User | hs_gori |
Language | Python (3.4.3) |
Score | 0 |
Code Size | 2053 Byte |
Status | RE |
Exec Time | 439 ms |
Memory | 25488 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt |
All | 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_min_01.txt | AC | 17 ms | 3064 KB |
00_min_02.txt | AC | 18 ms | 3064 KB |
00_min_03.txt | AC | 17 ms | 3064 KB |
00_min_04.txt | AC | 17 ms | 3064 KB |
00_min_05.txt | AC | 18 ms | 3064 KB |
00_min_06.txt | AC | 18 ms | 3064 KB |
00_min_07.txt | AC | 17 ms | 3064 KB |
00_min_08.txt | AC | 18 ms | 3064 KB |
00_sample_01.txt | AC | 18 ms | 3064 KB |
00_sample_02.txt | AC | 18 ms | 3064 KB |
00_sample_03.txt | AC | 18 ms | 3064 KB |
00_sample_04.txt | AC | 18 ms | 3064 KB |
00_sample_05.txt | AC | 18 ms | 3064 KB |
01_rnd_00.txt | AC | 109 ms | 7028 KB |
01_rnd_01.txt | RE | 253 ms | 25292 KB |
01_rnd_02.txt | RE | 270 ms | 25364 KB |
01_rnd_03.txt | RE | 231 ms | 25468 KB |
01_rnd_04.txt | RE | 247 ms | 25372 KB |
01_rnd_05.txt | AC | 107 ms | 7028 KB |
01_rnd_06.txt | AC | 190 ms | 20936 KB |
01_rnd_07.txt | RE | 279 ms | 25332 KB |
01_rnd_08.txt | AC | 111 ms | 7028 KB |
01_rnd_09.txt | AC | 106 ms | 7028 KB |
01_rnd_10.txt | AC | 360 ms | 14452 KB |
01_rnd_11.txt | AC | 108 ms | 7028 KB |
01_rnd_12.txt | AC | 157 ms | 18804 KB |
01_rnd_13.txt | RE | 261 ms | 25296 KB |
01_rnd_14.txt | AC | 110 ms | 7028 KB |
01_rnd_15.txt | RE | 327 ms | 25256 KB |
01_rnd_16.txt | AC | 108 ms | 7028 KB |
01_rnd_17.txt | AC | 439 ms | 20772 KB |
01_rnd_18.txt | AC | 106 ms | 7028 KB |
01_rnd_19.txt | RE | 252 ms | 25488 KB |
02_rndhard_00.txt | AC | 117 ms | 7156 KB |
02_rndhard_01.txt | AC | 123 ms | 7156 KB |
02_rndhard_02.txt | AC | 167 ms | 8180 KB |
02_rndhard_03.txt | AC | 167 ms | 8180 KB |
02_rndhard_04.txt | AC | 108 ms | 7028 KB |
02_rndhard_05.txt | AC | 104 ms | 7028 KB |
02_rndhard_06.txt | AC | 103 ms | 7028 KB |
02_rndhard_07.txt | AC | 110 ms | 7028 KB |
02_rndhard_08.txt | AC | 122 ms | 7412 KB |
02_rndhard_09.txt | AC | 127 ms | 7412 KB |
02_rndhard_10.txt | AC | 127 ms | 7412 KB |
02_rndhard_11.txt | AC | 128 ms | 7412 KB |
02_rndhard_12.txt | AC | 116 ms | 7284 KB |
02_rndhard_13.txt | AC | 124 ms | 7284 KB |
02_rndhard_14.txt | AC | 124 ms | 7540 KB |
02_rndhard_15.txt | AC | 134 ms | 7540 KB |
02_rndhard_16.txt | AC | 109 ms | 7028 KB |
02_rndhard_17.txt | AC | 110 ms | 7028 KB |
02_rndhard_18.txt | AC | 109 ms | 7156 KB |
02_rndhard_19.txt | AC | 111 ms | 7156 KB |
02_rndhard_20.txt | AC | 119 ms | 7156 KB |
02_rndhard_21.txt | AC | 110 ms | 7156 KB |
02_rndhard_22.txt | AC | 117 ms | 7412 KB |
02_rndhard_23.txt | AC | 116 ms | 7284 KB |
02_rndhard_24.txt | AC | 115 ms | 7156 KB |
02_rndhard_25.txt | AC | 107 ms | 7156 KB |
02_rndhard_26.txt | AC | 110 ms | 7156 KB |
02_rndhard_27.txt | AC | 115 ms | 7028 KB |
02_rndhard_28.txt | AC | 112 ms | 7156 KB |
02_rndhard_29.txt | AC | 107 ms | 7156 KB |
02_rndhard_30.txt | AC | 113 ms | 7028 KB |
02_rndhard_31.txt | AC | 114 ms | 7028 KB |
02_rndhard_32.txt | AC | 125 ms | 7284 KB |
02_rndhard_33.txt | AC | 124 ms | 7284 KB |
02_rndhard_34.txt | AC | 114 ms | 7156 KB |
02_rndhard_35.txt | AC | 112 ms | 7156 KB |
02_rndhard_36.txt | AC | 120 ms | 7156 KB |
02_rndhard_37.txt | AC | 111 ms | 7156 KB |
02_rndhard_38.txt | AC | 118 ms | 7156 KB |
02_rndhard_39.txt | AC | 111 ms | 7156 KB |
03_rndhardsmall_00.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_01.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_02.txt | AC | 18 ms | 3064 KB |
03_rndhardsmall_03.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_04.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_05.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_06.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_07.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_08.txt | AC | 17 ms | 3064 KB |
03_rndhardsmall_09.txt | AC | 17 ms | 3064 KB |