そろそろ時間もないので適当になりますが、paizaの問題を解説しましょう。
コードの解説
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の問題を読んでいるくらいなら標準入力は問題ないですね。
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:
もし配列の見ている場所が1であれば、その島に関する処理を行います。
ここでの処理は「島を発見したら、カウントを一つ増やしてその島を無くす（1を0に変換する。）」といった処理となります。
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
では一つずつ見ていきましょう。
input_line[j][i] = 0
a = [[i,j]]
まず、見ている場所を0にします。次にその場所の変数を配列aに格納します。ここで配列aが初期化されましたが、これは四方に1がないかを確認するための配列として使います。
while a:
x,y = a.pop()
配列aの中に配列がある限り回し続けます。pop()で配列の中身を抜き出して変数xと変数yにしています。こうしたほうが分かりやすい。
# 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が無いかを確認するためのものとなります。
# 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
見事に島がなくなっていますね。
n += 1
最後にカウンターである変数nに1を追加します。
これを入力された配列分、もといxとy分繰り返します。
print(n)
最後に変数nを出力して終了です。
ちなみに他の人の解法も別のアプローチをしているので、いろんな人の解法を見ていくのも勉強になると思います。
感想
これをC言語で解こうとしましたが、Visual Stdio CodeとWSL2がうまくつながっていないのか、再起動しないと赤線が消えないバグに見舞われています。コンパイルはできるんですがね・・・。
ところで、いつのまにC言語は可変長の配列を作れるようになったのですかっ！？
#include<stdio.h>
int main()
{
int a = 0;
scanf("%d",&a);
int b[a];
//これ、記憶上ではできなかったはずだが。それともcl.exeが対応してないだけ？
}