A33781. 翻卡片
题目描述
翻卡片
题目描述
小蓝在玩翻卡片游戏，每张卡片一面写着大写字母“A”，另一面写着大写字母“B”。首先将卡片排成一个N*N的矩阵。有的卡片是A面朝上，有的卡片是B面朝上。
现给定N的值，及N*N矩阵中每张卡片的状态，请你帮助小蓝挑选一张B面的卡，翻转成A面，使得翻转后的上、下、左、右四个方向相连的A面卡片最多，并将相连最多的卡片数量输出。
例如：N=3，3*3的矩阵中的卡片状态如下：
选择红框内那张B面卡片，翻转为A面，可以使翻转后四个方向相连的A面卡片最多，为5张。
输入描述
第一行输入一个正整数N（2≤N≤50），表示矩阵的行数和列数
第二行开始输入N行，每行输入N个字符（‘A’或者‘B’），表示矩阵中卡片状态，字符之间以一个空格隔开
输出描述
输出一个整数，表示翻转后矩阵中上、下、左、右四个方向相连的最多A面卡片张数
样例输入
3
A B B
A B A
B A B
样例输出
5
参考答案
#参考答案1
from copy import deepcopy
N=int(input())
grid=[]
for _ in range(N):
grid.append(input().split(','))
def max_area(new_grid,r,c):
if r<0 or r>=N or c<0 or c>=N:
return 0
if new_grid[r][c]!='A':
return 0
new_grid[r][c]='C'
return 1 + \
max_area(new_grid,r-1,c)+\
max_area(new_grid,r+1,c)+\
max_area(new_grid,r,c-1)+\
max_area(new_grid,r,c+1)
ans=0
for r in range(N):
for c in range(N):
if grid[r][c]=='B':
new_grid=deepcopy(grid)
new_grid[r][c]='A'
temp=max_area(new_grid,r,c)
ans=max(temp,ans)
print(ans)答案解析
参考答案2：
#参考答案2
def dfs(xx,yy):
s=1
fx=[[0,1],[0,-1],[1,0],[-1,0]]
for iii in range(4):
dx=xx+fx[iii][0]
dy=yy+fx[iii][1]
if(dx<0 or dx>=x or dy<0 or dy>=x):
continue
if(summ[dx][dy] or f[dx][dy]=='B'):
continue
summ[dx][dy]=1
s+=dfs(dx,dy)
#print(s,xx,yy)
return s
x=int(input())
f=[0]*x
summ=[0]*x
mx=0
for i in range(x):
f[i]=input().split(',')
summ[i]=[0]*x
for i in range(x):
for j in range(x):
if(f[i][j]=='B'):
#f[i][j]='A'
for xxx in range(x):
for yyy in range(x):
summ[xxx][yyy]=0
mx=max(mx,dfs(i,j))
#f[i][j]='B'
print(mx)