Problem:


島の数

地勢を示す縦 12, 横 12 のマスからなる平面図があります。おのおののマスは白か黒に塗られています。白は海を、黒は陸地を表します。二つの黒いマスが上下、あるいは左右に接しているとき、これらは地続きであるといいます。この平面図では、黒いマス一つのみ、あるいは地続きの黒いマスが作る領域を「島」といいます。例えば下図には、5 つの島があります。

■■■■□□□□■■■■
■■■□□□□□■■■■
■■□□□□□□■■■■
■□□□□□□□■■■■
□□□■□□□■□□□□
□□□□□□■■■□□□
□□□□□■■■■■□□
■□□□■■■■■■■□
■■□□□■■■■■□□
■■■□□□■■■□□□
■■■■□□□■□□□□
□□□□□□□□□□□□

マスのデータを読み込んで、島の数を出力するプログラムを作成してください。

Input

入力は複数のデータセットからなります。各データセットに１つの平面図が与えられます。黒いマスを 1、白いマスを 0 で表現した 12 個の数字の列 12 行でひとつの平面図を表します。データセットの間は１つの空行で区切られています。

データセットの数は 20 を超えません。

Output

データセットごとに、島の数を１行に出力します。

Sample Input

111100001111
111000001111
110000001111
100000001111
000100010000
000000111000
000001111100
100011111110
110001111100
111000111000
111100010000
000000000000

010001111100
110010000010
010010000001
010000000001
010000000110
010000111000
010000000100
010000000010
010000000001
010010000001
010010000010
111001111100

000000000000
111111111111
100010100001
100010100001
100010100001
100010100001
100100100101
101000011101
100000000001
100000000001
111111111111
100000000001

Output for the Sample Input

5
13
4

Hint

以下はサンプルインプットを■と□で表したものです。

■■■■□□□□■■■■　　□■□□□■■■■■□□　　□□□□□□□□□□□□
■■■□□□□□■■■■　　■■□□■□□□□□■□　　■■■■■■■■■■■■
■■□□□□□□■■■■　　□■□□■□□□□□□■　　■□□□■□■□□□□■
■□□□□□□□■■■■　　□■□□□□□□□□□■　　■□□□■□■□□□□■
□□□■□□□■□□□□　　□■□□□□□□□■■□　　■□□□■□■□□□□■
□□□□□□■■■□□□　　□■□□□□■■■□□□　　■□□□■□■□□□□■
□□□□□■■■■■□□　　□■□□□□□□□■□□　　■□□■□□■□□■□■
■□□□■■■■■■■□　　□■□□□□□□□□■□　　■□■□□□□■■■□■
■■□□□■■■■■□□　　□■□□□□□□□□□■　　■□□□□□□□□□□■
■■■□□□■■■□□□　　□■□□■□□□□□□■　　■□□□□□□□□□□■
■■■■□□□■□□□□　　□■□□■□□□□□■□　　■■■■■■■■■■■■
□□□□□□□□□□□□　　■■■□□■■■■■□□　　■□□□□□□□□□□■



Sample input:
111100001111
111000001111
110000001111
100000001111
000100010000
000000111000
000001111100
100011111110
110001111100
111000111000
111100010000
000000000000

010001111100
110010000010
010010000001
010000000001
010000000110
010000111000
010000000100
010000000010
010000000001
010010000001
010010000010
111001111100

000000000000
111111111111
100010100001
100010100001
100010100001
100010100001
100100100101
101000011101
100000000001
100000000001
111111111111
100000000001


Sample output:
5
13
4

Submission status: Runtime Error

Solution code:
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def main():
    while True:
        map = []
        count = 0
        try:
            for i in range(12):
                map.append([x for x in input()])

            for i in range(12):
                for j in range(12):
                    if map[i][j] == '1':
                        dfs(map, j, i)
                        count += 1
            print(count)
        except EOFError:
            break


def dfs(map, x, y):
    if x < 0 or y < 0 or x >= 12 or y >= 12:
        return

    map[y][x] = '0'
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if next_x >= 0 and next_x < 12 and next_y >= 0 and next_y < 12:
            if map[next_y][next_x] == '1':
                dfs(map, next_x, next_y)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
ID=0
def dfs(row,col):
    global ID
    if islands[row][col]==1:
        islandsID[row][col]==ID
        if row<11:
            dfs(row+1,col)
        if row>0:
            dfs(row-1,col)
        if col<11:
            dfs(row,col+1)
        if col>0:
            dfs(row,col-1)

while True:
    c=0
    islands=[]
    islandsID=[]
    for i in range(12):
        islands.append(list(map(int,input().split())))
    for _ in range(12):
        islandsID.append([0 for i in range(12)])
    
    for i in range(12):
        for j in range(12):
            if islands[i][j]==1 and islandsID[i][j]==0:
                ID+=1
            dfs(i,j)
    print(ID)
    try:
        c=input()
    except:
        break

Submission status: Runtime Error

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)

try:
    while True:
        s = input()#入力
        for i in range(len(s)):
            is_data[i] = list(is_data[i].strip())
        is_data = np.array(is_data).reshape(12,12)
except EOFError:
    print(counter())

Submission status: Runtime Error

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)
def get_map():
    is_data = []
    while True:
        try:
            tmp = list(int(input()))
            if len(tmp) != 12: break
            is_data.append(tmp)
        except:
            break
    return map
try:
    while True:
        is_data = get_map()
        if len(is_data) != 12: break
except EOFError:
    print(counter())

Submission status: Runtime Error

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)
while True:
    try:
        is_data=[]
        while True:
            s = list(input())#入力
            if not s :#空入力のときループぬける
                break
            is_data.append(s)
    except EOFError:
        print(counter())

Submission status: Runtime Error

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)
while True:
    try:
        is_data=[]
        while True:
            s = list(input())#入力
            if not s :#空入力のときループぬける
                break
            is_data.append(s)
    if len(is_data) != 12:break
    except EOFError:
        print(counter())

Submission status: Runtime Error

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                print(x,y)
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)

try:
    is_data=[]
    while True:
        s = input()#入力
        if not s :#空入力のときループぬける
            break
        is_data.append(s)
    for i in range(len(is_data)):
        is_data[i] = list(map(int,is_data[i]))
    is_data = np.array(is_data).reshape(12,12)
except EOFError:

print(counter())

Submission status: Runtime Error

Solution code:
def get_map():
  map = []
  while True:
    try:
      tmp = list(raw_input())
      if len(tmp) != 12: break
      map.append(tmp)
    except:
      break
  return map
def remove_island(x, y, map):
  map[x][y] = 0
  move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
  for i, j in move:
    if 0 <= x + i <= 11 and 0 <= y + j <= 11 and map[x + i][y + j] == '1':
      map = remove_island(x + i, y + j, map)
  return map[:]
while True:
  map = get_map()
  if len(map) != 12: break
  count = 0
  for x in range(12):
    for y in range(12):
      if map[x][y] == '1':
        count += 1
        map = remove_island(x, y, map)
  print count

Submission status: Runtime Error

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                print(x,y)
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)

try:
    is_data=[]
    while True:
        s = input()#入力
        if not s :#空入力のときループぬける
            break
        else:
            is_data.append(s)
    for i in range(len(is_data)):
        is_data[i] = list(map(int,is_data[i]))
    is_data = np.array(is_data).reshape(12,12)
except EOFError:
    print(counter())

Submission status: Runtime Error

Solution code:
import numpy as np
while 1:
    global a,c
    c = np.array([[0]*14]*14)
    a = np.array([[0]*14]*14)
    a[1:-1,1:-1] = [list(map(int,list(input()))) for i in range(12)]


    def dfs(x,y,n):
        if c[x][y] == 0 and a[x][y] == 1:
            c[x][y] = n
            [dfs(x+i, y+j, n) for i,j in [(-1,0),(1,0),(0,-1),(0,1)]]


    [[dfs(x,y,12*x + y) for x in range(1,12+1)] for y in range(1,12+1)]
    flat = [a for b in c for a in b]
    print(len(set(flat)) - 1)
    dump = input()
    #if input() ==

Submission status: Runtime Error

Solution code:
import numpy as np
while 1:
    global a,c
    c = np.array([[0]*14]*14)
    a = np.array([[0]*14]*14)
    a[1:-1,1:-1] = [list(map(int,list(input()))) for i in range(12)]


    def dfs(x,y,n):
        if c[x][y] == 0 and a[x][y] == 1:
            c[x][y] = n
            [dfs(x+i, y+j, n) for i,j in [(-1,0),(1,0),(0,-1),(0,1)]]


    [[dfs(x,y,12*x + y) for x in range(1,12+1)] for y in range(1,12+1)]
    flat = [a for b in c for a in b]
    print(len(set(flat)) - 1)
    if input() is None:
        break

Submission status: Runtime Error

Solution code:
import sys
def f(y,x):
    f=0
    if m[y][x]==1:
        m[y][x]=c
        f=1
    return f
def LR(y,x,dx):
    P=[]
    x+=dx
    while 0<=x<12 and m[y][x]!=0:
        if f(y,x):P+=[(y,x)]
        x+=dx
    return P
def UD(y,x,dy):
    P=[]
    y+=dy
    while 0<=y<12 and m[y][x]!=0:
        if f(y,x):P+=[(y,x)]
        y+=dy
    return P
def v1(buf):
    f=0
    while len(buf)>0:
        f=1
        y,x=buf.pop()
        m[y][x]=c
buf=list(set(buf+LR(y,x,-1)+LR(y,x,1)+UD(y,x,-1)+UD(y,x,1)))
    return f
def solve():
    global c
    buf=[]
    c=2
    for i in A:
        x=m[i]
        while x.count(1)>0:
            buf+=[(i,x.index(1))]
            if v1(buf):c+=1
    return c-2
A=range(12)
m=[[0 for x in A] for y in A]
y=0
for s in sys.stdin:
    if y<12:
        x=0
        for e in map(int,list(s[:-1])):
            m[y][x]=e
            x+=1
        y+=1
    else:
        print solve()
        y=0
print solve()

Submission status: Runtime Error

Solution code:
l = 12
def island(f,x,y,m):
    rf = f[:][:]
    if rf[y][x] == 1:
        rf[y][x] = m
        for i in [-1,1]:
            if 0 <= x+i <= l-1:
                rf = island(rf,x+i,y,m)
            if 0 <= y+i <= l-1:
                rf = island(rf,x,y+i,m)
    return rf

while True:
    f = []

    for i in range(l):
        f.append(map(int, list(raw_input())))
    for y in range(l):
        for x in range(l):
            f = island(f,x,y,m)
            m += 1

    m, ans = 2, []
    for i in range(l):
        for j in range(l):
            ans.append(f[i][j])
    print len(list(set(ans)))-1

    try   : raw_input()
    except: break

Submission status: Runtime Error

Solution code:
File Edit Options Buffers Tools Python Help
def island(f,x,y,m):
    if f[y][x] == 1:
        f[y][x] = m
        for i in [-1,1]:
            if 0 <= x+i <= 11:
                f = island(f,x+i,y,m)
            if 0 <= y+i <= 11:
                f = island(f,x,y+i,m)
    return f
while True:
    f = []; m = 2
    for i in range(12):
        f.append(map(int, list(raw_input())))
    for y in range(12):
        for x in range(12):
            if f[y][x]:
                f = island(f,x,y,m)
                m += 1
    ans = []
    for i in range(12):
        for j in range(12):
            ans.append(f[i][j])
    ans = list(set(ans))
    print len(ans) - 1*ans.count(0)
    try:raw_input()
    except: break

Submission status: Runtime Error

Solution code:
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
while True:
    ans = 0
    try:
        m = ['0'*14] + ['0'+raw_input()+'0' for i in xrange(12)] + ['0'*14]
        f = [[False for i in xrange(14)] for j in xrange(14)]
        for y in xrange(1, 13):
            for x in xrange(1, 13):
                if m[y][x]=='1' and f[y][x]==False:
                    q = [[x, y]]
                    f[y][x] = True
                    while len(q)>0:
                        px, py = q.pop(0)
                        for k in xrange(4):
                            nx = px + dx[k]; ny = py + dy[k];
                            if m[ny][nx]=='1' and f[ny][nx]==False:
                                f[ny][nx] = True
                                q.append([nx, ny])
                    ans += 1
        print ans
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;

int m[12][12];

bool valid(int y, int x){
  if(0 <= y && y < 12){
    if(0 <= x && x < 12){
        if(m[y][x] == 1) return true;
    }
  }
  return false;
}

void remove_island(int y, int x) {
  int nx, ny;
  int dx[4] = {1, 0, -1,  0};
  int dy[4] = {0, 1,  0, -1};

  m[y][x] = 0;
  for(int i = 0; i < 4; i++){
    ny = y + dy[i];
    nx = x + dx[i];
    if(valid(ny, nx)) remove_island(ny, nx);
  }
}

int main() {
  char c[12];
  int ans;
  while(1){
    for(int i = 0; i < 12; i++){
      if(!(cin >> c)) return 0;
      for(int j = 0; j < 12; j++){
        m[i][j] = (int)(c[j] - '0');
      }
    }

    ans = 0;
    for(int i = 0; i < 12; i++){
      for(int j = 0; j < 12; j++){
        if(valid(i, j)){
          remove_island(i, j);
          ans++;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}