Submission #3822685
Source Code Expand
h, w, t = map(int, input().split()) sw = [[''] * (w + 2)] Stt = [] End = [] for i in range(1, h + 1): tmp = [''] + list(input()) + [''] sw.append(tmp) for j in range(len(tmp)): if tmp[j] == 'S': Stt = [i, j] elif tmp[j] == 'G': End = [i, j] sw.append([''] * (w + 2)) def belmanford(x): count_sw = [[t + 1] * (w + 2) for _ in range(h + 2)] count_sw[Stt[0]][Stt[1]] = 0 next_turn = [Stt] while len(next_turn) != 0: n = next_turn.pop(0) for d in [[1, 0], [-1, 0], [0, 1], [0, -1]]: tmpn = [n[0] + d[0], n[1] + d[1]] if sw[tmpn[0]][tmpn[1]] == '': continue elif sw[tmpn[0]][tmpn[1]] == '#': if count_sw[n[0]][n[1]] + x < count_sw[tmpn[0]][tmpn[1]]: count_sw[tmpn[0]][tmpn[1]] = count_sw[n[0]][n[1]] + x next_turn.append(tmpn) else: if count_sw[n[0]][n[1]] + 1 < count_sw[tmpn[0]][tmpn[1]]: count_sw[tmpn[0]][tmpn[1]] = count_sw[n[0]][n[1]] + 1 next_turn.append(tmpn) if count_sw[End[0]][End[1]] <= t: return True else: return False bi_hi = t bi_lo = 0 while bi_hi - bi_lo != 1: tmp = (bi_hi - bi_lo) // 2 + bi_lo if (belmanford(tmp)): bi_lo = tmp else: bi_hi = tmp print(bi_lo)
Submission Info
Submission Time | |
---|---|
Task | C - 壁抜け |
User | mashinosatoshi |
Language | Python (3.4.3) |
Score | 100 |
Code Size | 1432 Byte |
Status | AC |
Exec Time | 31 ms |
Memory | 3192 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 40 / 40 | 30 / 30 | 30 / 30 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
Subtask1 | subtask0_sample_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt |
Subtask2 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt |
Subtask3 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt, subtask3_46.txt, subtask3_47.txt, subtask3_48.txt, subtask3_49.txt, subtask3_50.txt, subtask3_51.txt, subtask3_52.txt, subtask3_53.txt, subtask3_54.txt, subtask3_55.txt, subtask3_56.txt, subtask3_57.txt, subtask3_58.txt, subtask3_59.txt, subtask3_60.txt, subtask3_61.txt, subtask3_62.txt, subtask3_63.txt, subtask3_64.txt, subtask3_65.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 18 ms | 3192 KB |
subtask0_sample_02.txt | AC | 18 ms | 3188 KB |
subtask0_sample_03.txt | AC | 20 ms | 3188 KB |
subtask1_01.txt | AC | 18 ms | 3188 KB |
subtask1_02.txt | AC | 18 ms | 3192 KB |
subtask1_03.txt | AC | 18 ms | 3188 KB |
subtask1_04.txt | AC | 18 ms | 3188 KB |
subtask1_05.txt | AC | 18 ms | 3192 KB |
subtask1_06.txt | AC | 18 ms | 3192 KB |
subtask1_07.txt | AC | 18 ms | 3188 KB |
subtask1_08.txt | AC | 18 ms | 3188 KB |
subtask1_09.txt | AC | 18 ms | 3192 KB |
subtask1_10.txt | AC | 19 ms | 3192 KB |
subtask1_11.txt | AC | 18 ms | 3188 KB |
subtask1_12.txt | AC | 18 ms | 3192 KB |
subtask1_13.txt | AC | 19 ms | 3188 KB |
subtask1_14.txt | AC | 18 ms | 3188 KB |
subtask1_15.txt | AC | 18 ms | 3192 KB |
subtask2_16.txt | AC | 19 ms | 3192 KB |
subtask2_17.txt | AC | 20 ms | 3192 KB |
subtask2_18.txt | AC | 19 ms | 3192 KB |
subtask2_19.txt | AC | 19 ms | 3188 KB |
subtask2_20.txt | AC | 20 ms | 3192 KB |
subtask2_21.txt | AC | 20 ms | 3192 KB |
subtask2_22.txt | AC | 20 ms | 3192 KB |
subtask2_23.txt | AC | 20 ms | 3192 KB |
subtask2_24.txt | AC | 19 ms | 3188 KB |
subtask2_25.txt | AC | 19 ms | 3192 KB |
subtask2_26.txt | AC | 19 ms | 3192 KB |
subtask2_27.txt | AC | 18 ms | 3188 KB |
subtask2_28.txt | AC | 18 ms | 3192 KB |
subtask2_29.txt | AC | 19 ms | 3192 KB |
subtask2_30.txt | AC | 18 ms | 3192 KB |
subtask2_31.txt | AC | 18 ms | 3192 KB |
subtask2_32.txt | AC | 18 ms | 3192 KB |
subtask2_33.txt | AC | 19 ms | 3192 KB |
subtask2_34.txt | AC | 19 ms | 3192 KB |
subtask2_35.txt | AC | 20 ms | 3192 KB |
subtask2_36.txt | AC | 19 ms | 3192 KB |
subtask2_37.txt | AC | 20 ms | 3192 KB |
subtask2_38.txt | AC | 18 ms | 3188 KB |
subtask2_39.txt | AC | 19 ms | 3192 KB |
subtask2_40.txt | AC | 19 ms | 3192 KB |
subtask3_41.txt | AC | 19 ms | 3188 KB |
subtask3_42.txt | AC | 28 ms | 3192 KB |
subtask3_43.txt | AC | 24 ms | 3188 KB |
subtask3_44.txt | AC | 27 ms | 3192 KB |
subtask3_45.txt | AC | 31 ms | 3192 KB |
subtask3_46.txt | AC | 24 ms | 3188 KB |
subtask3_47.txt | AC | 26 ms | 3188 KB |
subtask3_48.txt | AC | 21 ms | 3188 KB |
subtask3_49.txt | AC | 29 ms | 3192 KB |
subtask3_50.txt | AC | 18 ms | 3192 KB |
subtask3_51.txt | AC | 24 ms | 3192 KB |
subtask3_52.txt | AC | 23 ms | 3188 KB |
subtask3_53.txt | AC | 20 ms | 3188 KB |
subtask3_54.txt | AC | 19 ms | 3192 KB |
subtask3_55.txt | AC | 19 ms | 3188 KB |
subtask3_56.txt | AC | 19 ms | 3188 KB |
subtask3_57.txt | AC | 18 ms | 3192 KB |
subtask3_58.txt | AC | 28 ms | 3188 KB |
subtask3_59.txt | AC | 25 ms | 3192 KB |
subtask3_60.txt | AC | 27 ms | 3192 KB |
subtask3_61.txt | AC | 19 ms | 3192 KB |
subtask3_62.txt | AC | 22 ms | 3192 KB |
subtask3_63.txt | AC | 18 ms | 3192 KB |
subtask3_64.txt | AC | 28 ms | 3192 KB |
subtask3_65.txt | AC | 23 ms | 3188 KB |