백준 2234 성곽

https://www.acmicpc.net/problem/2234

bfs문제이다.
문제에서 구하라는 3가지를 구하면 된다.
이 문제는 친히 비트를 쓰라고 알려주고 있다.
이전에 해왔던 bfs로 영역표시 알고리즘을 쓰는데, 이동하려는 칸에 막대가 있다면 이동을 안하면 된다.
영역구분을 했다면 1번과 2번은 정답을 구할 수 있고
3번은 땅 하나하나 탐색해가며 상하좌우에 본인 번호와 다른 칸이 있다면 두 칸을 더해보고 그 값이 제일 큰 값을 찾으면 된다.

from collections import deque
n,m = map(int,input().split())
arr = []
for i in range(m):
    arr.append(list(map(int,input().split())))
visited = [[0]*n for i in range(m)]
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = [0]*((n*m)+1)
def bfs():
    q = deque([])
    cnt = 0
    for i in range(m):
        for j in range(n):
            if not visited[i][j]:
                cnt += 1
                q.append((i,j))
                visited[i][j] = cnt
                while q:
                    x,y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx < 0 or nx >= m or ny < 0 or ny >= n:
                            continue
                        if arr[x][y] & (1<<k) or visited[nx][ny] != 0:
                            continue
                        visited[nx][ny] = cnt
                        q.append((nx,ny))
    return cnt
print(bfs())
for i in range(m):
    for j in range(n):
        ans[visited[i][j]] += 1
g = max(ans)
print(g)
cs = g
for i in range(m):
    for j in range(n):
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if arr[i][j] & (1<<k) and visited[i][j] != visited[nx][ny]:
                cs = max(cs, ans[visited[i][j]]+ans[visited[nx][ny]])
print(cs)