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: Wrong Answer

Solution code:
import itertools

def getPoint(m,x,y):
    if not (0 <= x < 12) or not (0 <= y < 12):
        return 0
    return m[y][x]

def setPoint(m,x,y,v):
    m[y][x] = v

while 1:
    try:
        m = [list(map(int,input().strip())) for _ in range(12)]
        count = 0
        empty = False
        while not empty:
            empty = True
            for x,y in itertools.product(range(12),repeat=2):
                if(getPoint(m,x,y)):
                    print(x,y)
                    count += 1
                    empty = False
                    q = []
                    q.append((x,y))
                    while q != []:
                        p = q.pop()
                        if(getPoint(m,p[0],p[1])):
                            setPoint(m,p[0],p[1],0)
                            for o in [(1,0),(-1,0),(0,1),(0,-1)]:
                                q.append((p[0] + o[0], p[1] + o[1]))
        print(count)
        input()
    except:
        exit()

Submission status: Wrong Answer

Solution code:
def fill(x, y, board):
    board[y][x] = 2
    points = [[y, x + 1], [y, x - 1], [y + 1, x], [y - 1, x]]
    # y
    if y == 0:
        points.remove([y-1, x])
    elif y == 11:
        points.remove([y+1, x])
    # x
    if x == 0:
        points.remove([y, x - 1])
    elif x == 11:
        points.remove([y, x + 1])
    for p in points:
        if board[p[0]][p[1]] == 1:
            board = fill(p[1], p[0], board)
    return board

islands = [list(map(int, list(input()))) for i in range(12)]
ans = 0

for y in range(12):
    for x in range(12):
        if islands[y][x] == 1:
            islands = fill(x, y, islands)
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def fill(x, y, board):
    board[y][x] = 2
    points = [[y, x + 1], [y, x - 1], [y + 1, x], [y - 1, x]]
    # y
    if y == 0:
        points.remove([y-1, x])
    elif y == 11:
        points.remove([y+1, x])
    # x
    if x == 0:
        points.remove([y, x - 1])
    elif x == 11:
        points.remove([y, x + 1])
    for p in points:
        if board[p[0]][p[1]] == 1:
            board = fill(p[1], p[0], board)
    return board

while True:
    try:
        islands = [list(map(int, list(input()))) for i in range(12)]
        input()
        ans = 0

        for y in range(12):
            for x in range(12):
                if islands[y][x] == 1:
                    islands = fill(x, y, islands)
                    ans += 1
        print(ans)
    except:
        break

Submission status: Wrong Answer

Solution code:
import sys

def quartet(h, w):
    global flag
    if 0 <= h <= 11 and 0 <= w <= 11:
        if mapp[h][w] == '1':
            mapp[h][w] = '$'
            flag = True
            bigbang(h, w)
        elif mapp[h][w] == '2' or mapp[h][w] == '$':
            return
    else:
        return

def bigbang(h, w):
    quartet(h, w+1)
    quartet(h-1,w)
    quartet(h, w-1)
    quartet(h+1, w)

mapp = []
for line in sys.stdin:
    lis = []
    for char in line.rstrip():
        lis.append(char)
    else:
        mapp.append(lis)

flag = False
count = 0
for h in range(12):
    for w in range(12):
        if quartet(h, w):
            count += 1
else:
    print count

Submission status: Wrong Answer

Solution code:
import sys

def quartet(h, w):
    global flag
    if 0 <= h <= 11 and 0 <= w <= 11:
        if mapp[h][w] == '1':
            mapp[h][w] = '$'
            flag = True
            bigbang(h, w)
        elif mapp[h][w] == '0' or mapp[h][w] == '$':
            return
    else:
        return

def bigbang(h, w):
    quartet(h, w+1)
    quartet(h-1,w)
    quartet(h, w-1)
    quartet(h+1, w)

mapp = []
for line in sys.stdin:
    lis = []
    for char in line.rstrip():
        lis.append(char)
    else:
        mapp.append(lis)

flag = False
count = 0
for h in range(12):
    for w in range(12):
        if quartet(h, w):
            count += 1
else:
    print count

Submission status: Wrong Answer

Solution code:
import sys

def quartet(h, w):
    global flag
    if 0 <= h <= 11 and 0 <= w <= 11:
        if mapp[h][w] == '1':
            mapp[h][w] = '$'
            flag = True
            bigbang(h, w)
        elif mapp[h][w] == '0' or mapp[h][w] == '$':
            return
    else:
        return

def bigbang(h, w):
    quartet(h, w+1)
    quartet(h-1,w)
    quartet(h, w-1)
    quartet(h+1, w)

mapp = []
for line in sys.stdin:
    lis = []
    for char in line.rstrip():
        lis.append(char)
    else:
        mapp.append(lis)

flag = False
count = 0
for h in range(12):
    for w in range(12):
        quartet(h, w)
        if flag == True:
            count += 1
        flag = False
else:
    print count

Submission status: Wrong Answer

Solution code:
def f1():
    t = 0
    for y, line in enumerate(M):
        for x, cell in enumerate(line):
            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(input()))
    except EOFError:
        print(f1())
        break

Submission status: Wrong Answer

Solution code:
class Depth_First_Search_stack:
    def __init__(self, map):
        self.map = map
        self.num_island = 0
        self.stack = []
        self.start_point = None

    def get_start_point(self):
        get_start = False
        for i in range(12):
            for j in range(12):
                if self.map[i][j] == '1':
                    self.start_point = [i, j]
                    get_start = True
        return get_start

    def check(self, new_r, new_c):
        return 0<=new_r<12 and 0<=new_c<12 and self.map[new_r][new_c] == '1'

    def search(self, r, c):
        while self.stack:
            r, c = self.stack.pop()
            self.map[r][c] = '0'
            for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                if self.check(r+i, c+j):
                    self.stack.append([r+i, c+j])

    def run(self):
        while self.get_start_point():
            r, c = self.start_point
            self.stack.append([r, c])
            self.search(r, c)
            self.num_island += 1

if __name__ == '__main__':
    map = []
    for i in range(12):
        row = [x for x in input()]
        map.append(row)
    DFS = Depth_First_Search_stack(map)
    DFS.run()
    print(DFS.num_island)

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

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:
    is_data = []
    while True:
        tmp = list(input())
        if len(tmp)!=12 :break
    is_data.append(tmp)
except EOFError:
    print(counter())

Submission status: Wrong Answer

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 is_data
try:
    while True:
        is_data = get_map()
        if len(is_data) != 12: break
except EOFError:
    print(counter())

Submission status: Wrong Answer

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():
    land_data = []
    while True:
        try:
            tmp = list(int(input()))
            if len(tmp) != 12: break
            land_data.append(tmp)
        except:
            break
    return land_data
try:
    while True:
        is_data = get_map()
        if len(is_data) != 12: break
except EOFError:
    print(counter())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

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): print('r=', arr[r])

	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: Wrong Answer

Solution code:
import sys

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

while True:
    uf = UnionFind(14 * 14);
    board = [];
    while True:
        try:
            s = raw_input();
        except:
            sys.exit(0);
        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));

Submission status: Wrong Answer

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:
    m, f =2, []
    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

    ans = []
    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: Wrong Answer

Solution code:
W,H = 12,12
dxy = [[1,0],[0,1],[-1,0],[0,-1]]
def solve(field,w,h):
	if 0 <= w < W and 0 <= h < H and field[h][w] == 1:
		field[h][w] = 0
		for dx,dy in dxy:
			solve(field,w+dx,h+dy)

while 1:
	try:
		field = [map(int,raw_input().split()) for i in range(H)]
		ans = 0
		for h in range(H):
			for w in range(W):
				if field[h][w] == 1:
					solve(field,w,h)
					ans += 1
		print ans
	except:
		break

Submission status: Memory Limit Exceeded

Solution code:
class Depth_First_Search_stack:
    def __init__(self, map):
        self.map = map
        self.num_island = 0
        self.stack = []
        self.start_point = None

    def get_start_point(self):
        get_start = False
        for i in range(12):
            for j in range(12):
                if self.map[i][j] == '1':
                    self.start_point = [i, j]
                    get_start = True
        return get_start

    def check(self, new_r, new_c):
        return 0<=new_r<12 and 0<=new_c<12

    def search(self, r, c):
        self.stack.append(self.start_point)
        while self.stack:
            r, c = self.stack.pop()
            self.map[r][c] = '0'
            for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                if self.check(r+i, c+j):
                    self.stack.append([r+i, c+j])

    def run(self):
        while self.get_start_point():
            r, c = self.start_point
            self.search(r, c)
            self.num_island += 1

if __name__ == '__main__':
    for t in range(20):
        stop_flag = False
        map = []
        for i in range(12):
            row = [x for x in input()]
            if i==0:
                if len(row) != 12:
                    stop_flag = True
                    break
            map.append(row)

        if stop_flag:
            break

        DFS = Depth_First_Search_stack(map)
        DFS.run()
        print(DFS.num_island)
        empty = input()

Submission status: Accepted

Solution code:
from collections import deque
dq = deque()
append, popleft = dq.append, dq.popleft
try:
    while True:
        a = [[0]*14] + [[0]+list(map(int,input()))+[0] for _ in [0]*12] + [[0]*14]
        result = 0
        for y in range(1, 13):
            for x in filter(lambda x: a[y][x], range(1, 13)):
                result += 1
                a[y][x] = 0
                dq.clear()
                append((x, y))
                while dq:
                    cx, cy = popleft()
                    for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0)):
                        if a[cy+dy][cx+dx]:
                            a[cy+dy][cx+dx] = 0
                            append((cx+dx, cy+dy))
        print(result)
        input()

except EOFError:
    pass

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:
import itertools

def getPoint(m,x,y):
    if not (0 <= x < 12) or not (0 <= y < 12):
        return 0
    return m[y][x]

def setPoint(m,x,y,v):
    m[y][x] = v

while 1:
    try:
        m = [list(map(int,input().strip())) for _ in range(12)]
        count = 0
        empty = False
        while not empty:
            empty = True
            for x,y in itertools.product(range(12),repeat=2):
                if(getPoint(m,x,y)):
                    count += 1
                    empty = False
                    q = []
                    q.append((x,y))
                    while q != []:
                        p = q.pop()
                        if(getPoint(m,p[0],p[1])):
                            setPoint(m,p[0],p[1],0)
                            for o in [(1,0),(-1,0),(0,1),(0,-1)]:
                                q.append((p[0] + o[0], p[1] + o[1]))
        print(count)
        input()
    except:
        exit()

Submission status: Accepted

Solution code:
def fill(x, y, board):
    board[y][x] = 2
    points = [[y, x + 1], [y, x - 1], [y + 1, x], [y - 1, x]]

    if y == 0:
        points.remove([y-1, x])
    elif y == 11:
        points.remove([y+1, x])
    if x == 0:
        points.remove([y, x - 1])
    elif x == 11:
        points.remove([y, x + 1])

    for p in points:
        if board[p[0]][p[1]] == 1:
            board = fill(p[1], p[0], board)
    return board

while True:
    try:
        islands = [list(map(int, list(input()))) for i in range(12)]
        ans = 0

        for y in range(12):
            for x in range(12):
                if islands[y][x] == 1:
                    islands = fill(x, y, islands)
                    ans += 1
        print(ans)
        input()
    except:
        break

Submission status: Accepted

Solution code:
import itertools
import sys

def delete(ya,xa,lis):
    lis[ya][xa] = 0
    move = [[-1,0],[0,-1],[1,0],[0,1]]
    for x,y in move:
        if 0<=xa+x<=11 and 0<=ya+y<=11 and lis[ya+y][xa+x]=='1':
            delete(ya+y,xa+x,lis)

def sol(a,b,lis):
    for i,j in itertools.product(xrange(12),repeat=2):
        if lis[i][j]=='1':
            m[i][j] = 1
            delete(i,j,lis)

while True:
    try:
        l = [[ 0 for i in xrange(12) ] for j in xrange(12) ]
        m = [[ 0 for i in xrange(12) ] for j in xrange(12) ]
        d = []
        for i in xrange(12):
            d.append(list(raw_input()))
        sol(0,0,d)
        print sum([1 for e in m for f in e if f])
        raw_input()
    except:
        break

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

MAX_Y = 12
MAX_X = 12

XY =  ((-1, 0), (1, 0), (0, -1), (0, 1))

def main():
    # input
    while(True):
        try:
            data = []
            for j in range(MAX_Y):
                input_list = map(int, raw_input())
                data.append(input_list)
            print(countIsland(data))
            raw_input()
        except EOFError:
            break

def countIsland(data):
    cnt = [0]
    def countIsland_(data):
        land = findIsland(data)
        if len(land) == 0:
            return cnt[0]
        else:
            data = sinkIsland(data, land)
            cnt[0] = cnt[0] + 1
            return countIsland_(data)

    return countIsland_(data)

# sink adjasent Island.
def sinkIsland(data, land):
    if isIn(*land):
        if not data[land[1]][land[0]] == 0:
            data[land[1]][land[0]] = 0
            lands = [(k[0] + land[0], k[1] + land[1]) for k in XY]
            for x in lands:
                data = sinkIsland(data, x)

    return data

def findIsland(data):
    for y in range(MAX_Y):
        for x in range(MAX_X):
            if data[y][x] == 1:
                return (x, y)
    else:
        return ()

# decision inner board.
def isIn(x, y):
    return 0<=x<MAX_X and 0<=y<MAX_Y

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
f = sys.stdin


def paintout0(islands, x, y):
    if 0 <= x <12 and 0 <= y <12 and islands[y][x]:
        islands[y][x] = 0
        paintout0(islands,x + 1,y)
        paintout0(islands,x,y + 1)
        paintout0(islands,x -1,y)
        paintout0(islands,x,y -1)

while True:
    islands = [[int(c) for c in f.readline().strip()] for _ in range(12)]
    cnt =0
    for y in range(len(islands)):
        for x in range(len(islands[0])):
            if islands[y][x]:
                cnt += 1
                paintout0(islands,x,y)
    print(cnt)
    
    if not f.readline():
        break

Submission status: Accepted

Solution code:
import sys

def quartet(h, w):
    global flag
    if 0 <= h <= 11 and 0 <= w <= 11:
        if mapp[h][w] == '1':
            mapp[h][w] = '$'
            flag = True
            bigbang(h, w)
        elif mapp[h][w] == '0' or mapp[h][w] == '$':
            return
    else:
        return

def bigbang(h, w):
    quartet(h, w+1)
    quartet(h-1,w)
    quartet(h, w-1)
    quartet(h+1, w)

mapp = []
for line in sys.stdin:
    if not line == '\n':
        lis = []
        for char in line.rstrip():
            lis.append(char)
        else:
            mapp.append(lis)
    if len(mapp) == 12:
        flag = False
        count = 0
        for h in range(12):
            for w in range(12):
                quartet(h, w)
                if flag == True:
                    count += 1
                flag = False
        else:
            print count
            mapp = []

Submission status: Accepted

Solution code:
def fact(y, x1, x2):
	island[y] = island[y][:x1] + "0" + island[y][x2:]
	if island[y-1][x1:x2] == "1":
		fact(y-1, x1, x2)
	if island[y+1][x1:x2] == "1":
		fact(y+1, x1, x2)
	if island[y][x1-1:x2-1] == "1":
		fact(y, x1 - 1, x2 - 1)
	if island[y][x1+1:x2+1] == "1":
		fact(y, x1 + 1, x2 + 1)

while True:
	island = []
	for _ in xrange(12):
		island.append(raw_input())
	
	island.insert(0, "00000000000000")
	island.append("00000000000000")
	for i in xrange(12):
		island[i+1] = "0" + island[i+1] + "0"
	
	count = 0
	for i in xrange(12):
		for j in xrange(12):
			if island[i+1][j+1:j+2] == "1":
				fact(i+1, j+1, j+2)
				count += 1
		
	print count
	try:
		raw_input()
	except EOFError:
		break

Submission status: Accepted

Solution code:
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0

def sol(l,a,b):
    q=[[a,b]]
    while len(q):
        chk=q.pop()
        for y,x in xy:
            try:
                t1,t2=chk[0]+y,chk[1]+x
                if l[t1][t2]==1 and 0<=t1<12 and 0<=t2<12:
                    q.append([t1,t2])
                    l[t1][t2]=0
            except:
                pass
    return l
while 1:
    l=[]
    try:
        for i in range(12):
            l.append([int(x) for x in raw_input()])
        ans=0
        for i in range(12):
            for j in range(12):
                if l[i][j]==1:
                    l[i][j]=0
                    ans+=1
                    l=sol(l,i,j)
        print ans
        raw_input()
    except:
        break
exit()

Submission status: Accepted

Solution code:
N = 12
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

def dfs(i, j):
    field[i][j] = '0'
    for k in xrange(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < N and 0 <= nj < N and field[ni][nj] == '1':
            dfs(ni, nj)
    return;

while True:
    try:
        field = []
        for i in xrange(N):
            field.append(list(raw_input()))
        cnt = 0
        for i in xrange(N):
            for j in xrange(N):
                if field[i][j] == '1':
                    dfs(i, j)
                    cnt += 1
        print cnt
        raw_input()
    except:
        break

Submission status: Accepted

Solution code:
def search_neighbor(sea, x, y):
    global dir_x, dir_y
    for i in range(4):
        nx, ny = x + dir_x[i], y + dir_y[i]
        if not 0 <= nx < 12 or not 0 <= ny < 12:
            continue
        if sea[ny][nx]:
            sea[ny][nx] = 0
            search_neighbor(sea, nx, ny)


dir_x = (1, -1, 0, 0)
dir_y = (0, 0, 1, -1)

while True:
    sea = [[int(i) for i in input()] for _ in range(12)]
    count = 0

    for i in range(144):
        x, y = i % 12, i // 12
        if sea[y][x]:
            sea[y][x] = 0
            search_neighbor(sea, x, y)
            count += 1

    print(count)

    try:
        input()
    except:
        break

Submission status: Accepted

Solution code:
def f1():
    t = 0
    for y, line in enumerate(M):
        for x, cell in enumerate(line):
            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'
        for i in range(4):
            if i == 0:  # U
                f2(x, y-1)
            elif i == 1:  # D
                f2(x, y+1)
            elif i == 2:  # R
                f2(x+1, y)
            elif i == 3:  # L
                f2(x-1, y)


def get_input():
    while True:
        try:
            yield input()
        except EOFError:
            break
            

M = []
for line in list(get_input()):
    if line == '':
        print(f1())
        M = []
    else:
        M.append(list(line))
print(f1())

Submission status: Accepted

Solution code:
def f1():
    t = 0
    for y, line in enumerate(M):
        for x, cell in enumerate(line):
            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)


def get_input():
    while True:
        try:
            yield input()
        except EOFError:
            break


M = []
for line in list(get_input()):
    if line == '':
        print(f1())
        M = []
    else:
        M.append(list(line))
print(f1())

Submission status: Accepted

Solution code:
def f1():
    t = 0
    for y, line in enumerate(M):
        for x, cell in enumerate(line):
            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