mtsmfm blog

オフラインリアルタイムどう書く E04 の問題 - ドキドキ登山

オフラインリアルタイムどう書く E04 の問題です。

問題

次の図は山を上から見たところである。

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2512:C

A ~ H が登山者、1 ~ 8 は方角、実線が登山道である。

A ~ H のうち登頂できた人を求めたい。

ルール

登山には次のルールがある:

  1. 登山道を麓から頂上に向かって登る
  2. 登る際に、横方向の登山道があればそちらを通る

ただし、一部の登山道は頂上からの落石によって通行止めになっており、通行止めに行きあたると登頂失敗になる。

落石は、頂上から登山者と同じルールで麓まで転がってくる。

先述した例 (2512:C) だと、通行止めの道は次の図の赤破線のようになる。

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2512:C

よって、頂上に辿りつけた人は次の図の赤丸のようになる。

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2512:C

入力

2512:C のような形式。 コロンの前は頂上と並行に伸びる登山道の情報。頂上から順に並んでいる。 コロンの後は落石の開始位置。

出力

DEFGH のような形式。登頂に成功した人をアルファベット順で並べる。

補足

実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

#入力期待状況へのリンク
02512:CDEFGH状況
11:ACDEFGH状況
2:CABDEFGH状況
32345:BAGH状況
41256:EABCDH状況
51228:AADEFG状況
65623:BAEFGH状況
78157:CABDEFGH状況
874767:EABCFGH状況
988717:DABCEFGH状況
10148647:AACDEFH状況
11374258:HBCDEFH状況
126647768:FABCDEH状況
134786317:EABFGH状況
143456781:C状況
15225721686547123:CCEF状況
162765356148824666:FABCDEH状況
1742318287535641783:FBDE状況
18584423584751745261:DFGH状況
198811873415472513884:DCFG状況
2074817442725737422451:HBCDEF状況
21223188865746766511566:CABGH状況
222763666483242552567747:FABCG状況
2376724442325377753577138:EEG状況
24327328486656448784712618:B状況
254884637666662548114774288:DDGH状況
2684226765313786654637511248:HDEF状況
27486142154163288126476238756:ACDF状況
281836275732415226326155464567:FBCD状況
2962544434452376661746517374245:GG状況
30381352782758218463842725673473:BA状況

テストデータ

状況一覧

2512:C

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2512:C

1:A

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 1:A

:C

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 :C

2345:B

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2345:B

1256:E

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 1256:E

1228:A

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 1228:A

5623:B

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 5623:B

8157:C

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 8157:C

74767:E

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 74767:E

88717:D

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 88717:D

148647:A

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 148647:A

374258:H

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 374258:H

6647768:F

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 6647768:F

4786317:E

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 4786317:E

3456781:C

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 3456781:C

225721686547123:C

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 225721686547123:C

2765356148824666:F

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2765356148824666:F

42318287535641783:F

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 42318287535641783:F

584423584751745261:D

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 584423584751745261:D

8811873415472513884:D

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 8811873415472513884:D

74817442725737422451:H

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 74817442725737422451:H

223188865746766511566:C

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 223188865746766511566:C

2763666483242552567747:F

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 2763666483242552567747:F

76724442325377753577138:E

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 76724442325377753577138:E

327328486656448784712618:B

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 327328486656448784712618:B

4884637666662548114774288:D

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 4884637666662548114774288:D

84226765313786654637511248:H

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 84226765313786654637511248:H

486142154163288126476238756:A

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 486142154163288126476238756:A

1836275732415226326155464567:F

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 1836275732415226326155464567:F

62544434452376661746517374245:G

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 62544434452376661746517374245:G

381352782758218463842725673473:B

頂上 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8入力 381352782758218463842725673473:B
comments powered by Disqus