https://www.acmicpc.net/problem/4963
문제를 잘 읽어야한다.
가로 + 세로 + 대각선 으로 연결되어 있는 사각형이 걸어갈 수 있는 곳이다.
문제를 대충 읽어서 가로 + 세로만 연결되어 있다고,,, 봤다 (삽질⛏)
graph[(x,y)] = []
graph[(x,y)].append((nx,ny))
for node in graph: cnt += dfs(node,0)
cnt += dfs((nx,ny),cnt)
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
def dfs(node,cnt):
x, y = node[0], node[1]
if visited[x][y] == 0:
visited[x][y] = 1
while graph[node]:
next_node = graph[node].pop()
nx, ny = next_node[0], next_node[1]
cnt += dfs((nx,ny),cnt)
return 1
else:
return 0
while (1):
w, h = map(int,input().rstrip().rsplit())
if w==0 and h==0 : break
island, graph = [], {}
visited = [[0] * w for _ in range(h)]
cnt = 0
# 하, 상, 좌, 우 , 상좌, 상우, 하좌, 하우
dx = [1, -1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
for _ in range(h):
row = input().rstrip()
row = row.replace(' ','')
island.append(row)
for i,row in enumerate(island):
for j,check in enumerate(row):
if check == '1':
graph[(i,j)] = []
for k in range(8):
nx = i + dx[k]
ny = j + dy[k]
if 0 <= nx < h and 0 <= ny < w:
if island[nx][ny] == '1':
graph[(i,j)].append((nx,ny))
for node in graph:
cnt += dfs(node,0)
print(cnt)