Pythonで解いたっpaizaのキャンペーン対象問題（Sランク「島探し」）

そろそろ時間もないので適当になりますが、paizaの問題を解説しましょう。

https://paiza.jp/works/mondai/s_rank_skillcheck_sample/search-island

## コードの解説

```py
def main():
	xy = list(map(int,input().split()))
	input_line = [list(map(int,input().split())) for _ in range(xy[1])]
	n = 0
	for i in range(xy[0]): # x軸
		for j in range(xy[1]): # y軸
			if input_line[j][i] == 1:
				input_line[j][i] = 0
				a = [[i,j]]
				while a:
					x,y = a.pop()
					# Up
					if y != 0 and input_line[y-1][x] == 1:
						input_line[y-1][x] = 0
						a.append([x,y-1])
					# Donw
					if y != xy[1]-1 and input_line[y+1][x] == 1:
						input_line[y+1][x] = 0
						a.append([x,y+1])
					# Left
					if x != 0 and input_line[y][x-1] == 1:
						input_line[y][x-1] = 0
						a.append([x-1,y])
					# Right
					if x != xy[0]-1 and input_line[y][x+1] == 1:
						input_line[y][x+1] = 0
						a.append([x+1,y])
				n += 1
	print(n)
main()
```
問題文では0が海、1が陸と分類しています。ということで、1がどのくらいあるのかというコードを作っていきます。

まず変数の初期化です。RANK Sの問題を読んでいるくらいなら標準入力は問題ないですね。
```py
	xy = list(map(int,input().split()))
	input_line = [list(map(int,input().split())) for _ in range(xy[1])]
	n = 0
```
問題はここからです。どうやって島を探査しますか？
これはいろいろありそうですが、ここは四か所見てつながっているか見ていきましょう。
```py
	for i in range(xy[0]): # x軸
		for j in range(xy[1]): # y軸
```
回す分です。配列の長さ分探査します。
```py
            if input_line[j][i] == 1:
```
もし配列の見ている場所が1であれば、その島に関する処理を行います。
ここでの処理は「島を発見したら、カウントを一つ増やしてその島を無くす（1を0に変換する。）」といった処理となります。
```py
				input_line[j][i] = 0
				a = [[i,j]]
				while a:
					x,y = a.pop()
					# Up
					if y != 0 and input_line[y-1][x] == 1:
						input_line[y-1][x] = 0
						a.append([x,y-1])
					# Donw
					if y != xy[1]-1 and input_line[y+1][x] == 1:
						input_line[y+1][x] = 0
						a.append([x,y+1])
					# Left
					if x != 0 and input_line[y][x-1] == 1:
						input_line[y][x-1] = 0
						a.append([x-1,y])
					# Right
					if x != xy[0]-1 and input_line[y][x+1] == 1:
						input_line[y][x+1] = 0
						a.append([x+1,y])
				n += 1
```
では一つずつ見ていきましょう。

```py
				input_line[j][i] = 0
    			a = [[i,j]]
```
まず、見ている場所を0にします。次にその場所の変数を配列aに格納します。ここで配列aが初期化されましたが、これは四方に1がないかを確認するための配列として使います。
```py
				while a:
					x,y = a.pop()
```
配列aの中に配列がある限り回し続けます。pop()で配列の中身を抜き出して変数xと変数yにしています。こうしたほうが分かりやすい。
```py
					# Up
					if y != 0 and input_line[y-1][x] == 1:
						input_line[y-1][x] = 0
						a.append([x,y-1])
					# Donw
					if y != xy[1]-1 and input_line[y+1][x] == 1:
						input_line[y+1][x] = 0
						a.append([x,y+1])
					# Left
					if x != 0 and input_line[y][x-1] == 1:
						input_line[y][x-1] = 0
						a.append([x-1,y])
					# Right
					if x != xy[0]-1 and input_line[y][x+1] == 1:
						input_line[y][x+1] = 0
						a.append([x+1,y])

```
このコードが四方に1が無いかを確認するためのものとなります。
```py
					# Up
					if y != 0 and input_line[y-1][x] == 1:
						input_line[y-1][x] = 0
						a.append([x,y-1])
```
もし、端っこではなく今いる座標の上が1であるならば、その位置にある1を0にし配列aにその座標を格納します。

端っことはどういうことか、入力例1を使って説明しましょう。
```
0 1 1 0
1 0 1 0
1 0 0 0
0 0 1 1
0 1 1 1
```
例えば、`y = 0`のときに上を見た場合`y = -1`となるのでなにもない領域を見ることになります。
```
//ここを見ているけど、なにもないよ！
0 1 1 0
1 0 1 0
1 0 0 0
0 0 1 1
0 1 1 1
```
それを防ぐために`y != 0`を行って、yが0にある場合はこの処理を無視するといった動きにしています。これを全ての端っこで行うようにします。
ちなみに周辺を0で囲むのであれば、この処理を入れなくても可能です。
```
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 1 0 0
0 1 0 0 0 0
0 0 0 1 1 0
0 0 1 1 1 0
0 0 0 0 0 0
```
その場合、枠内にある入力されたマスだけを見る処理に変更しましょう。

この処理を四方に向かって確認をします。これが起きた時、どのように変化するのか確認しましょう。なお、ここでは分かりやすいように変化した数値は9に変えています。
```
0 1 1 0
1 0 1 0
1 0 0 0
0 0 1 1
0 1 1 1
```
これが変化のない状態です。
```
0 9 1 0
1 0 1 0
1 0 0 0
0 0 1 1
0 1 1 1

a = [1,0]
```
[1,0]の1がありました。これを9に変えます。また、配列aに今の座標を格納します。
```
0 9 9 0
1 0 1 0
1 0 0 0
0 0 1 1
0 1 1 1

a = [2,0]
```
格納された場所から四方に見ると右側に1がありました。ということでこの場所を0にし、配列aにこの座標を格納します。
```
0 9 9 0
1 0 9 0
1 0 0 0
0 0 1 1
0 1 1 1

a = [2,1]
```
格納された場所から四方に見ると下側に1がありました。ということでこの場所を0にし、配列aにこの座標を格納します。
```
0 9 9 0
1 0 9 0
1 0 0 0
0 0 1 1
0 1 1 1

a = //なにもないよ
```
さきほどの座標から四方に見ても1がありません。ということで、これで一つの島であることが確認できました。
なお、実際にはこうなっています。
```
0 0 0 0
1 0 0 0
1 0 0 0
0 0 1 1
0 1 1 1
```
見事に島がなくなっていますね。

```py
				n += 1
```
最後にカウンターである変数nに1を追加します。
これを入力された配列分、もといxとy分繰り返します。
```py
	print(n)
```
最後に変数nを出力して終了です。

ちなみに他の人の解法も別のアプローチをしているので、いろんな人の解法を見ていくのも勉強になると思います。

https://qiita.com/rA9-S/items/25316d5fda2c058bcb71

## 感想
これをC言語で解こうとしましたが、Visual Stdio CodeとWSL2がうまくつながっていないのか、再起動しないと赤線が消えないバグに見舞われています。コンパイルはできるんですがね・・・。
ところで、いつのまにC言語は可変長の配列を作れるようになったのですかっ！？
```c
#include<stdio.h>
int main()
{
    int a = 0;
    scanf("%d",&a);
    int b[a];
    //これ、記憶上ではできなかったはずだが。それともcl.exeが対応してないだけ？
}
```