砂漠中の最短距離のオアシスを見つける問題

**＜アルゴリズム問題シリーズ（Python）＞**

#１．はじめに
同一ファイル内で入力から出力を実施する方法としてはhttps://qiita.com/ajim/items/4d350710ba70056f5f6f を参考にしました。

```py
import sys
import io


_INPUT = """\
5 4
1
3
4
5
"""
sys.stdin = io.StringIO(_INPUT)
```
・`sys`モジュールはインタプリタで使用・管理している変数や、インタプリタの動作に深く関連する関数を定義しています。`sys.stdin`はインタプリタが使用する、それぞれ標準入力、標準出力、および標準エラー出力の ファイルオブジェクト であり、stdin は (input() の呼び出しも含む) すべての対話型入力に使われます。https://docs.python.org/ja/3/library/sys.html
・io モジュールは様々な種類の I/O を扱う Python の主要な機能を提供しています。StringIO オブジェクトはインメモリーのテキストストリームです。
`io.StringIO(initial_value='', newline='\n')`のように使用し、バッファの初期値を initial_value で与えることが出来ます。改行変換を有効にすると、改行コードは write() によってエンコードされます。ストリームはバッファの開始位置に配置されます。https://docs.python.org/ja/3/library/io.html?highlight=io#io.StringIO

#２．問題（難度：2（/5））
主人公ショルツは砂漠の中で現在地Xにおり、縦方向と横方向にのみ動くことができる。
ショルツから脱水症状だと連絡を受けたあなたは彼の現在地から最も近いオアシスを探すプログラムを考え、彼を助けようとしている。
彼から砂漠の地図（A行B列の大きさを持ち、その中にC個のオアシスが存在する）が入力として送られてくるので、出力例に倣って最短距離のオアシスの個数とそのオアシス番号を出力として返しなさい。
ただし、最短距離とは、現在地からオアシスへ移動する際の最小の移動回数であり、移動は縦方向と横方向のみ可能であることに注意せよ。
最短距離のオアシスが複数ある場合は、オアシス番号が小さい順に出力せよ。

**地図中の地形要素（入力ファイルに記載されている）**
・&：砂地
・1~Cまでの整数：オアシス、その数字がオアシス番号を表す
・X：ショルツの現在地

入出力は以下のようになる。
##入力
```py
A B C  ##A行B列の地図中にオアシスがC個ある。
map_1  #地図の1行目
map_2
...
map_A  #地図のA行目
```
##出力
```py
N          #最短距離となるオアシス数
oasis_1    #最短距離となるオアシスの番号を昇順に出力する。
oasis_2
...
oasis_N
 ```
##例
```py
入力
6 5 6    #6行5列の地図中にオアシスが6つある。
&&&1&    #地図の1列目
&X&&&    #Xが現在地(2,2)
&&&&4    #数字がオアシス
5&6&&
&&3&&
2&&&&    #地図の6列目
出力
3        #最短距離となるオアシス数
1        #最短距離となるオアシスの番号を昇順に出力する。
5
6
この場合、現在地X(2,2)から最短となる距離3の位置にオアシス 1,5,6 が存在するため出力のようになる。
```


#３．解答
```py
import io
import sys

_INPUT = """\
6 5 6
&&&1&
&X&&&
&&&&4
5&6&&
&&3&&
2&&&&
"""
sys.stdin = io.StringIO(_INPUT)

A,B,C = map(int,input().split())
map = [[i for i in input()] for j in range(A)]
#print(map) #[['&', '&', '&', '1', '&'], ['&', '&', '&', '&', '&'], ['&', '&', '&', '&', '4'], ['5', '&', '6', '&', '&'], ['&', '&', '3', '&', '&'], ['2', '&', '&', '&', '&']]
oasis = {}
X = {}
for i in range(A):
    for j in range(B):
        if map[i][j] != '&' and map[i][j] != 'X':
            oasis[map[i][j]] = i+1, j+1
        elif map[i][j] == 'X':
            X[map[i][j]] = i+1, j+1
#print(oasis) #{'1': (1, 4), '4': (3, 5), '5': (4, 1), '6': (4, 3), '3': (5, 3), '2': (6, 1)}
#print(X)     #{'X': (2, 2)}
distance = {key:abs(X['X'][0]-oasis[key][0])+abs(X['X'][1]-oasis[key][1]) for key in oasis}
#print(distance) #{'1': 3, '4': 4, '5': 3, '6': 3, '3': 4, '2': 5}
print(list(distance.values()).count(min(distance.values()))) #3
nearest_oasis = [int(key) for key in distance if distance[key] == min(distance.values())]
#print(nearest_oasis) #[1, 5, 6]
for i in range(len(nearest_oasis)):
    print(sorted(nearest_oasis)[i])
#1
#5
#6
        
```

#４．メモ、学んだこと
**・文字列のスライス**
`val = "いろはにほへと散りぬるを"`、`val[0] 'い'`、`val[3:7] 'にほへと'`

**・辞書の基礎と内包表記**
`辞書.keys()`、`辞書.values()`
`distance = {key:abs(X['X'][0]-oasis[key][0])+abs(X['X'][1]-oasis[key][1]) for key in oasis}`

**・タプルの基礎**
要素の取り出しはリストと同じ。

**・特定要素の数**
`['aa', 'bb', 'cc', 'aa', 'bb'].count('aa')　2`
count()は特定の文字（列）の個数が返却されるだけだが、collectionsモジュールのCounter() を使うと、どの要素が何個あるか簡単に調べることができる。戻り値は辞書型になる。
https://hibiki-press.tech/python/count/103#toc5

**・リストの要素を昇順または降順に並び替える**
`sorted(リスト)`は元のリストが消えない。
`リスト.sort()`は元のリストは参照できなくなる。


**・zip関数の基礎**
2つの要素から同時に値を習得できる。
https://dot-blog.jp/news/python-dict-comprehensions/


#５．参考文献
https://docs.python.org/ja/3/library/sys.html

https://docs.python.org/ja/3/library/io.html?highlight=io#io.StringIO

https://qiita.com/Ma_AtoP/items/63ec026b3b373b7f84c1

https://qiita.com/ajim/items/4d350710ba70056f5f6f

https://techacademy.jp/magazine/23323

https://maku77.github.io/python/list/count.html

https://www.javadrive.jp/python/list/index11.html

https://dot-blog.jp/news/python-dict-comprehensions/

#６．ご意見・ご感想をお待ちしております
当方、未熟なプログラマーのため、よりよいコード等ありましたら教えていただけると幸いです。
皆様のメッセージをお待ちしております。