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: Accepted

Solution code:
def f1():
    t = 0
    for y in range(len(M)):
        for x in range(len(M[0])):
            if M[y][x] == '1':
                f2(x, y)
                t += 1
    return t


def f2(x, y):
    if x < 0 or len(M[0]) == x or y < 0 or len(M) == y:
        return
    if M[y][x] == '1':
        M[y][x] = '0'
        f2(x, y-1)
        f2(x, y+1)
        f2(x+1, y)
        f2(x-1, y)


M = []
while True:
    try:
        line = input()
        if line == '':
            print(f1())
            M = []
        else:
            M.append(list(line))
    except EOFError:
        print(f1())
        break

Submission status: Accepted

Solution code:
def check(y,x):
	if 0<=y<=11 and 0<=x<=11:
		return True
	return False
	
def dfs(y,x):
	if g[y][x]=="0":return 0
	g[y][x]="0"
	for i in xrange(4):
		nexty=y+dy[i]
		nextx=x+dx[i]
		if  not check(nexty,nextx):continue
		if visited[nexty][nextx]==0 and g[nexty][nextx]=="1":
			visited[nexty][nextx]=1
			dfs(nexty,nextx)
	return 1
	
dx=(1,0,-1,0)
dy=(0,1,0,-1)
while 1:
	try:
		g=[[] for _ in xrange(12)]
		for i in xrange(12):
			for j in raw_input():
				g[i].append(j)
		cnt=0
		visited=[[0]*12 for _ in xrange(12)]
		for i in xrange(12):
			for j in xrange(12):
				cnt+=dfs(i,j)
		print(cnt)
		raw_input()
	except:
		break

Submission status: Accepted

Solution code:
H, W = 12, 12
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
field = []

def solver(x, y):
  global field
  if x < 0 or y < 0 or x >= H or y >= W:
    return
  for dx, dy in dxy:
    if x+dx < 0 or y+dy < 0 or x+dx >= H or y+dy >= W:
      continue
    if field[x+dx][y+dy] == 1:
      field[x+dx][y+dy] = 0
      solver(x+dx, y+dy)

while True:
  field = []
  for i in xrange(H):
    field.append(map(int, raw_input()))

  ans = 0
  for x in xrange(H):
    for y in xrange(W):
      if field[x][y] == 1:
        solver(x, y)
        ans += 1
  print ans
  try:
    raw_input()
  except EOFError:
    break

Submission status: Accepted

Solution code:
import sys

def solve(f, i, j):
    if 0<=i<12 and 0<=j<12 and f[j][i] == 1:
        f[j][i] = 0
        for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]: solve(f, i+dx, j+dy)

while True:
    field = [[int(c) for c in sys.stdin.readline().strip()] for _ in range(12)]
    ans = 0
    for i in range(12):
        for j in range(12):
            if field[j][i] == 1:
                solve(field,i,j)
                ans += 1
    print(ans)
    if not sys.stdin.readline(): break

Submission status: Accepted

Solution code:
c=0
def f(a,x,y):
    if 0<=x<12 and 0<=y<12 and a[y][x]=='1':
        a[y][x]='0'
        for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:f(a,x+dx,y+dy)

while 1:
    try:
        if c:input()
    except:break
    a = [list(input()) for _ in [0]*12]
    c=1;b=0
    for i in range(12):
        for j in range(12):
            if a[j][i]=='1':
                b+=1;f(a,i,j)
    print(b)

Submission status: Accepted

Solution code:
def f(a,x,y):
    if 0<=x<12 and 0<=y<12 and a[y][x]=='1':
        a[y][x]='0'
        for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:f(a,x+dx,y+dy)

while 1:
    try:
        a=[list(input()) for _ in [0]*12]
        b=0
        for i in range(12):
            for j in range(12):
                if a[j][i]=='1':
                    b+=1;f(a,i,j)
        print(b);input()
    except:break

Submission status: Accepted

Solution code:
#!usr/bin/env python3

import sys


def eliminate_ones(grid, row, col):
    if 0 <= row < 12 and 0 <= col < 12 and grid[row][col] == 1:
        grid[row][col] = 0
        eliminate_ones(grid, row+1, col)
        eliminate_ones(grid, row-1, col)
        eliminate_ones(grid, row, col+1)
        eliminate_ones(grid, row, col-1)


def main():
    while True:
        grid = [[int(num) for num in sys.stdin.readline().strip()]
                for _ in range(12)]

        num_of_islands = int()

        for row in range(len(grid)):
            for col in range(len(grid[row])):
                if grid[row][col] == 1:
                    num_of_islands += 1
                    eliminate_ones(grid, row, col)

        print(num_of_islands)

        if not sys.stdin.readline():
            break


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(i, j, m):
    '''
    m[i][j]??¨????????£??????????????°????????????????????????
    '''
    m[i][j] = 0
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ni = i + di
        nj = j + dj
        if ni in range(12) and nj in range(12) and m[ni][nj] == 1:
            dfs(ni, nj, m)                

while True:
    try:
        m = [list(map(int, list(input()))) for _ in range(12)]

        count = 0
        for i in range(12):
            for j in range(12):
                if m[i][j] == 1:
                    count += 1
                    dfs(i, j, m)
        
        print(count)
        input()
    except:
        break

Submission status: Accepted

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

def dfs(y,x,vis,S):
    vis [y] [x] = True
    for i in range(len(dx)):
        ny = y + dy [i]
        nx = x + dx [i]
        if (ny >= 0 and ny < N and nx >= 0 and nx < N) == False:
            continue
        if S [ny] [nx] == '1' and vis [ny] [nx] == False:
            dfs(ny,nx,vis,S)

while True:
    S = []
    for i in range(N):
        S.append(input())
    
    ans = 0
    vis = [[False] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if S [i] [j] == '1' and vis [i] [j] == False:
                dfs(i,j,vis,S)
                ans += 1

    print(ans)
    try:
        input()
    except EOFError:
        break

Submission status: Accepted

Solution code:
def remove_linked(x, y, DATA):
    DATA[x][y]=0# clear
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]#left, right, down, up
    for i, j in move:
        nx,ny=x+i,y+j#next x and y
        if -1<nx<12 and -1<ny<12 and DATA[nx][ny]:
            DATA=remove_linked(nx, ny, DATA)
    return DATA

while 1:
    DATA = [[int(x) for x in list(input())] for _ in range(12)]
    count = 0
    for x in range(12):
        for y in range(12):
            if DATA[x][y]:
                count += 1
                DATA = remove_linked(x, y, DATA)
    print (count)
    
    try:input()
    except:break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

def solve(island):
    visited = []
    for lst in island:
        visit_row = []
        for c in lst:
            if c == '1':
                visit_row.append(False)
            else:
                visit_row.append(True)
        visited.append(visit_row)

    def paintable(x, y):
        if 0 <= x < 12 and 0 <= y < 12 and not visited[x][y]:
            return True
        else:
            return False

    def paint(x, y, number):
        visited[x][y] = True
        island[x][y] = number
        if paintable(x-1, y):
            paint(x-1, y, number)

        if paintable(x+1, y):
            paint(x+1, y, number)

        if paintable(x, y-1):
            paint(x, y-1, number)

        if paintable(x, y+1):
            paint(x, y+1, number)

    paint_id = 2

    for i in range(12):
        for j in range(12):
            if paintable(i, j):
                paint(i, j, paint_id)
                paint_id += 1

    line = []
    for lst in island:
        line += lst

    line = set(line)
    if '0' in lst:
        line.remove('0')

    print(len(line))

for s in sys.stdin:
    s = s.strip()
    if s != '':
        island = [list(s)]
        for i in range(11):
            s = input().strip()
            island.append(list(s))
        solve(island)
    else:
        island = []
        pass

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067
"""
import sys


def solve(map):
    num_of_land = 0
    work = []
    lmap = map[:]
    for i in range(1, len(map)):
        for j in range(1, len(map[0])):
            if lmap[i][j] == 1:
                num_of_land += 1
                work.append([i, j])
                lmap[i][j] = 0

                while work:
                    y, x = work.pop()
                    if lmap[y][x+1] == 1: #  ????????????
                        work.append([y, x+1])
                        lmap[y][x+1] = 0
                    if lmap[y+1][x] == 1: #  ????????????
                        work.append([y+1, x])
                        lmap[y+1][x] = 0
                    if lmap[y][x-1] == 1: #  ????????????
                        work.append([y, x-1])
                        lmap[y][x-1] = 0

    return num_of_land


def main(args):
    data = [
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],

    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    [0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    [0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
            ]
    data = []
    buff = []
    for line in sys.stdin:
        line = line.strip()
        if line:
            if len(buff) == 0:
                buff = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
            line = '0' + line + '0'
            buff.append([int(x) for x in line])
        else:
            if len(buff) > 0:
                buff.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
                data.append(buff)
                buff = []
    if len(buff) > 0:
        buff.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
        data.append(buff)
        buff = []

    for map in data:
        result = solve(map)
        print(result)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067
"""
import sys
import copy

def solve(map):
    num_of_land = 0
    work = []
    lmap = copy.deepcopy(map)
    for i, line in enumerate(lmap[1:], start=1):
        while 1 in line[1:-1]:
            j = line.index(1)
            num_of_land += 1
            work.append([i, j])
            lmap[i][j] = 0

            while work:
                y, x = work.pop()
                if lmap[y][x+1] == 1: #  ????????????
                    work.append([y, x+1])
                    lmap[y][x+1] = 0
                if lmap[y+1][x] == 1: #  ????????????
                    work.append([y+1, x])
                    lmap[y+1][x] = 0
                if lmap[y][x-1] == 1: #  ????????????
                    work.append([y, x-1])
                    lmap[y][x-1] = 0
    return num_of_land


def main(args):
    # data = [
    # [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    # [0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    # [0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
    # [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
    # [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    # [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
    # [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    # [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    # [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    # [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    # [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
    # [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
    # [0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
    # 
    # [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    # [0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    # [0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    # [0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    # [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
    # [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    # [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    # [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    # [0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    # [0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
    # [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    # [0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
    #         ]
    data = []
    buff = []
    for line in sys.stdin:
        line = line.strip()
        if line:
            if len(buff) == 0:
                buff = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
            line = '0' + line + '0'
            buff.append([int(x) for x in line])
        else:
            if len(buff) > 0:
                buff.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
                data.append(buff)
                buff = []
    if len(buff) > 0:
        buff.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
        data.append(buff)
        buff = []

    for map in data:
        result = solve(map)
        print(result)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def main():
    while True:
        map = []
        count = 0
        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)

        if not sys.stdin.readline():
            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: Accepted

Solution code:
# Aizu Problem 0067: The Number of Islands
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


class UndirectedGraph():
    def __init__(self, grid):
        offsets = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        N = len(grid)
        M = len(grid[0])
        self.edges = {}
        self.nodes = []
        for row in range(N):
            for col in range(M):
                if grid[row][col] == '1':
                    self.AddNode((row, col))
                    for row_off, col_off in offsets:
                        row2 = row + row_off
                        col2 = col + col_off
                        if 0 <= row2 < N and 0 <= col2 < M and  grid[row2][col2] == '1':
                                self.AddEdge((row, col), (row2, col2))
        
    def AddNode(self, node):
        if node not in self.nodes:
            self.nodes.append(node)
        if node not in self.edges:
            self.edges[node] = []

    def GetNodes(self):
        return self.nodes

    def GetEdges(self):
        return self.edges

    def AddEdge(self, node1, node2):
        self.AddNode(node1)
        self.AddNode(node2)
        if node1 not in self.edges[node2]:
            self.edges[node2].append(node1)
        if node2 not in self.edges[node1]:
            self.edges[node1].append(node2)

    def Degree(self, node):
        return len(self.edges[node])

    def GetNeighbors(self, node):
        return self.edges.get(node, [])
            
    def GetPath(self, source, target):
        # find path by BFS:
        predecessor = {node: -1 for node in self.GetNodes()}
        predecessor[source] = 0
        visited = {node: False for node in self.GetNodes()}
        queue = [source]
        while len(queue) > 0:
            current = queue.pop(0)
            visited[current] = True
            for neighbor in self.GetNeighbors(current):
                if not visited[neighbor] and neighbor not in queue:
                    queue.append(neighbor)
                    predecessor[neighbor] = current
                if neighbor == target:
                    queue = []
                    break
        # build path from predecessor info:
        if predecessor[target] == -1:
            return []
        path = [target]
        while path[0] != source:
            path = [predecessor[path[0]]] + path[:]
        return path

    def GetConnectedComponents(self):
        # identify connected components by BFS
        nodes = self.GetNodes()[:]
        connected_components = []
        while len(nodes) > 0:
            queue = [nodes.pop()]
            component = [queue[0]]
            while len(queue) > 0:
                current = queue.pop(0)
                for neighbor in self.GetNeighbors(current):
                    if neighbor in nodes and neighbor not in queue:
                        queue.append(neighbor)
                        nodes.remove(neighbor)
                        component.append(neighbor)
            connected_components.append(component)
        return connected_components


finished = False
while True:
    grid = []
    if finished:
        break
    while True:
        try:
            inp = input().strip()
        except EOFError:
            finished = True
            break
        if len(inp) == 0:
            break
        grid.append([_ for _ in inp])
    G = UndirectedGraph(grid)
    print(len(G.GetConnectedComponents()))

Submission status: Accepted

Solution code:
while True:
    c=0
    islands=[]
    islandsID=[]
    ID=0

    def dfs(row,col):
        global ID
        if 0<=row<12 and 0<=col<12:
            if islands[row][col]==1 and islandsID[row][col]==0:
                islandsID[row][col]=ID
                for dr, dc in [[0,1],[1,0],[0,-1],[-1,0]]:
                    dfs(row+dr,col+dc)

    for i in range(12):
        islands.append(list(int(k) for k in input()))
    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: Accepted

Solution code:
def paint(map_inp, x, y):
    if map_inp[y][x]:
        map_inp[y][x] = False
        if map_inp[y][x - 1]:
            map_inp = paint(map_inp, x - 1, y)
        if map_inp[y][x + 1]:
            map_inp = paint(map_inp, x + 1, y)
        if map_inp[y - 1][x]:
            map_inp = paint(map_inp, x, y - 1)
        if map_inp[y + 1][x]:
            map_inp = paint(map_inp, x, y + 1)
    return map_inp

while True:
    try:
        m = [[False for i in range(14)] for j in range(14)]
        for i in range(12):
            inp = input()
            for j in range(12):
                if inp[j] == "1":
                    m[i + 1][j + 1] = True

        cnt = 0
        for i in range(12):
            for j in range(12):
                if m[i + 1][j + 1]:
                    m = paint(m, j + 1, i + 1)
                    cnt += 1
        print(cnt)
        inp = input()
    except:
        break

Submission status: Accepted

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

def nuri(table, m, x, y):
    if table[x-1][y] and m[x-1][y] == 0:
        m[x-1][y] = m[x][y]
        nuri(table, m, x-1, y)
    if table[x+1][y] and m[x+1][y] == 0:
        m[x+1][y] = m[x][y]
        nuri(table, m, x+1, y)
    if table[x][y-1] and m[x][y-1] == 0:
        m[x][y-1] = m[x][y]
        nuri(table, m, x, y-1)
    if table[x][y+1] and m[x][y+1] == 0:
        m[x][y+1] = m[x][y]
        nuri(table, m, x, y+1)
    return

N = list(get_input())
for l in range(0,len(N),13):
    table = [[False for i in range(14)] for j in range(14)]
    for i in range(12):
        for j in range(12):
            if int(N[l+i][j]) == 1:
                table[i+1][j+1] = True

    m = [[0 for i in range(14)] for j in range(14)]

    cnt = 0
    for i in range(1,13):
        for j in range(1,13):
            if table[i][j] and m[i][j] == 0:
                cnt += 1
                m[i][j] = cnt
                nuri(table, m, i, j)

    print(cnt)

Submission status: Accepted

Solution code:
while True:
  lst = []
  for i in range(12):
    ls = []
    s = input()
    for j in range(12):
      ls.append(int(s[j]))
    lst.append(ls)
  xd = [0,1,0,-1]
  yd = [1,0,-1,0]
  count = 0
  def check(pt):
    if 11 < pt[0] or pt[0] < 0 or 11 < pt[1] or pt[1] < 0:
      return False
    elif(lst[pt[0]][pt[1]] == 1):
      lst[pt[0]][pt[1]] = 0
      for i in range(4):
        check([pt[0]+xd[i],pt[1]+yd[i]])
      return True
    else:
      return False
  def printMap():
    for i in range(12):
      st = ""
      for j in range(12):
        st = st + str(lst[i][j])
      print(st)
    print()
  for x in range(12):
    for y in range(12):
      if lst[x][y]:
        check([x,y])
        count += 1
        #printMap()
  print(count)
  try:
    input()
  except EOFError:
    break

Submission status: Accepted

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(len(is_data)):
        for y in range(len(is_data)):
            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) 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)

is_data=[]
while True:
    try:
        s = list(input())#入力
        if not s:#空入力のときループぬける
            print(counter())
            is_data=[]
            s = []
        else:
            #ls = len(s)
            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(ls,ls)
#print(is_data)
    except EOFError:
        print(counter())
        break

Submission status: Accepted

Solution code:
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(len(is_data)):
        for y in range(len(is_data)):
            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) 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)

is_data=[]
while True:
    try:
        s = list(input())#入力
        if not s:#空入力のとき
            print(counter())
            is_data=[]
            s = []
        else:
            is_data.append(s)
    except EOFError:
        print(counter())
        break

Submission status: Accepted

Solution code:
direct = ((0, -1), (0, 1), (-1, 0), (1, 0)) #移動方向

def search(x, y, mp): 
  if mp[x][y] == "1": #1を見つけたら0に書き換える
    mp[x][y] = "0"
    for dx, dy in direct: #4方向について繰り返す
      search(x + dx, y + dy, mp)
 
while True:
  #mp...全体のマップ、上下左右を0で囲っておく
  mp = [list("0" + input() + "0") for _ in range(12)]
  mp.insert(0, [0] * 14)
  mp.append([0] * 14)

  ans = 0

  for x in range(1, 13):
    for y in  range(1, 13):
      if mp[x][y] == "1":
        ans += 1
        search(x, y, mp)

  print(ans)

  try:
    input()
  except EOFError:
    break

Submission status: Accepted

Solution code:
# AOJ 0067 The Number of Island
# Python3 2018.6.16 bal4u

# UNION-FIND library
MAX = 12*12

id, size = [0]*MAX, [0]*MAX

def init(n):
	for i in range(n): id[i], size[i] = i, 1
	
def root(i):
	while i != id[i]:
		id[i] = id[id[i]]
		i = id[i]
	return i
	
def connected(p, q):
	return root(p) == root(q)
	
def unite(p, q):
	i, j = root(p), root(q)
	if i == j: return
	if size[i] < size[j]:
		id[i] = j
		size[j] += size[i]
	else:
		id[j] = i
		size[i] += size[j]
# UNION-FIND library

arr = [[0 for r in range(12)] for c in range(12)]
dr = [-1, 0, 1, 0]
dc = [ 0, 1, 0,-1]

while True:
	init(12*12)
	for r in range(12): arr[r] = list(map(int, input()))

	for r in range(12):
		for c in range(12):
			if arr[r][c] == 0: continue
			for i in range(4):
				nr, nc = r + dr[i], c + dc[i]
				if nr >= 0 and nr < 12 and nc >= 0 and nc < 12:
					if arr[nr][nc] == 1:
						unite(r*12+c, nr*12+nc)
	
	ans = 0
	for r in range(12):
		for c in range(12):
			if arr[r][c] == 1 and root(r*12+c) == r*12+c: ans += 1

	print(ans)
	try: input()
	except: break

Submission status: Accepted

Solution code:
def dfs(board,y,x):
    if not board[y][x]:
        return 0
    board[y][x]=0
    dx,dy=[0,1,0,-1],[1,0,-1,0]
    for i in xrange(4):
        dfs(board,y+dy[i],x+dx[i])
    return 1
while True:
    try:
        board=[[0]+map(int,raw_input()[:])+[0] for unused in xrange(12)]
        board.insert(13,[0]*14)
        board.insert(0,[0]*14)
        print sum([dfs(board,i/12+1,i%12+1) for i in xrange(12*12)])
        raw_input()
    except:
        break

Submission status: Accepted

Solution code:
import sys


def solv(boad):
    boad = map(lambda x: [0] + x + [0], boad)
    boad.insert(0, [0] * 14)
    boad.append([0] * 14)
    n = sum([foo(boad, x, y) for x in xrange(1, 13) for y in xrange(1, 13)])
    return n


def foo(b, x, y):
    if b[y][x]:
        b[y][x] = 0
        foo(b, x-1, y)
        foo(b, x+1, y)
        foo(b, x, y-1)
        foo(b, x, y+1)
        return 1
    else:
        return 0



boads = []
b = []
for line in sys.stdin:
    line = line.rstrip()
    if line == '':
        boads.append(b)
        b = []
        continue
    b.append(map(int, line))
boads.append(b)
for boad in boads:
    print solv(boad)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def solve(L):
    n = 0
    sets = set()
    for y in range(12):
        for x in range(12):
            if not L[y][x]:
                continue
            elif y and L[y-1][x]:
                L[y][x] = L[y-1][x]
            elif x and L[y][x-1]:
                L[y][x] = L[y][x-1]
            else:
                n += 1
                sets.add(n)
                L[y][x] = n
        for x in range(10, -1, -1):
            if L[y][x] and L[y][x+1] and L[y][x] != L[y][x+1]:
                sets.discard(L[y][x])
                L[y][x] = L[y][x+1]
    return len(sets)

s = '\n'
sep = '\n'
while s:
    L = []
    for i in range(12):
        L.append([int(s) for s in stdin.readline().rstrip()])
    print(solve(L))
    s = stdin.readline()

Submission status: Accepted

Solution code:

class UnionFind(object):
    def __init__(self, size):
        self.data = [-1 for i in range(size)];
    
    def unite(self, x, y):
        x = self.root(x);
        y = self.root(y);
        if (x != y):
            if (self.data[y] < self.data[x]):
                x, y = y, x;
            self.data[x] += self.data[y];
            self.data[y] = x;
        return x != y;

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def root(self, x):
        if self.data[x] < 0 :
            return x;
        self.data[x] = self.root(self.data[x]);
        return self.data[x];
    
    def size(self, x):
        return -self.data[self.root(x)];


def pos(i, j):
    return i * 14 + j

end_flag = False
while True:
    uf = UnionFind(14 * 14);
    board = [];
    while True:
        try:
            s = raw_input();
        except:
            end_flag = True
            break
        s = "0" + s.strip() + "0";
        if (s == "00"):
            break;
        board.append(list(s));

    sent = [0 for i in range(len(board[0]))]
    board = [sent] + board + [sent];
    #print board

    island = 0
    for i in range(1, len(board) - 1):
        for j in range(1, len(board[0]) - 1):
            if board[i][j] == '1':
                p = pos(i, j);
                f = False;
                if (board[1 + i][j] == '1'):
                    uf.unite(p, pos(i + 1, j));
                    f = True;
                if (board[i - 1][j] == '1'):
                    uf.unite(p, pos(i - 1, j));
                    f = True;
                if (board[i][j + 1] == '1'):
                    uf.unite(p, pos(i, j + 1));
                    f = True;
                if (board[i][j - 1] == '1'):
                    uf.unite(p, pos(i, j - 1));
                    f = True;
                if not f:
                    island += 1
    
    print island + len(filter(lambda x: x < -1, uf.data));
    if end_flag:
        break;