恶心的造墙题
flood fill用bfs对方块染色并计数就行
难点在于如何把给的数据用一个图形表示出来,步骤如下
首先初始一个 宽为2n-1 长为2m-1的方格区域
对于每行方格,偶数下标位置表示空间,奇数位置表示缝隙,墙只能放在空袭上(缝隙用0表示)
对于每一个输入的数据,它的空间在棋盘中的位置为(2i,2j)其空间标记为1,找出对应四面放墙的情况,之后向四周放墙标记为3
最后,对于棋盘上出现连个墙相邻的情况,需要将中间缝隙也设置为墙:例如3 0 3改为3 3 3(横竖都要改)
完成棋盘建立后,进行flood filll即可
python版本
from collections import deque
def bfs(i,j):
global ans
res = 1
queue = deque()
queue.append((i,j))
board[i][j] = 3
while queue:
sam = queue.popleft()
x = sam[0]
y = sam[1]
for var in ways_4:
n_x = x + var[0]
n_y = y + var[1]
if n_x < n_n and n_x >= 0 and n_y < n_m and n_y >= 0 and board[n_x][n_y] != 3:
if board[n_x][n_y] == 1:
res += 1
board[n_x][n_y] = 3
queue.append((n_x,n_y))
ans = max(res,ans)
ways = {0:[],
1:[(0,-1)],2:[(-1,0)],4:[(0,1)],8:[(1,0)],
3:[(0,-1),(-1,0)],5:[(0,-1),(0,1)],9:[(0,-1),(1,0)],6:[(-1,0),(0,1)],10:[(-1,0),(1,0)],12:[(0,1),(1,0)],
7:[(0,-1),(-1,0),(0,1)],11:[(0,-1),(-1,0),(1,0)],13:[(0,-1),(0,1),(1,0)],14:[(-1,0),(0,1),(1,0)],
15:[(0,-1),(-1,0),(0,1),(1,0)]}
ways_4 = [(0,1),(0,-1),(1,0),(-1,0)]
n,m = map(int,input().split())
n_n = 2*n - 1
n_m = 2*m - 1
board = [[0]*(n_m) for i in range(n_n)]
for i in range(n):
temp = [int(_) for _ in input().split()]
for j in range(m):
num = temp[j]
x = i*2
y = j*2
board[x][y] = 1
for var in ways[num]:
n_x = x + var[0]
n_y = y + var[1]
if n_x >= 0 and n_x < n_n and n_y >=0 and n_y < n_m:
board[n_x][n_y] = 3
for i in range(n_n):
for j in range(n_m):
if i - 1 >= 0 and i + 1 < n_n:
if board[i - 1][j] == 3 and board[i + 1][j] == 3 and board[i][j] != 1:
board[i][j] = 3
if j - 1 >= 0 and j + 1 < n_m:
if board[i][j - 1] == 3 and board[i][j + 1] == 3 and board[i][j] != 1:
board[i][j] = 3
fang = 0
ans = 0
for i in range(n_n):
for j in range(n_m):
if board[i][j] == 1:
fang += 1
bfs(i,j)
print(fang)
print(ans)
'''
for i in range(n_n):
print(board[i])
'''