D27-蓝桥杯

今天是烤蓝桥前的最后一天了！！还有很多别的事情要做！！！
早上先看了一下y总的floodfill算法。

原本以为dfs会困难，没想到竟然比bfs简单这么多。

现在是8:42，打算实现一下这个代码。

1233

dfs调了半天，终于通了，但是超时了
需要注意：
1、连通块判断条件：界内+未被搜索过+是陆地

# from copy import deepcopy
import sys 
sys.setrecursionlimit(1000000)

n = int(input())
g = [[0]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    g[i][1:] = list(input())
st = [[False]*(n+1) for _ in range(n+1)]
directions = [[1,0],[-1,0],[0,1],[0,-1]]

def dfs(i,j):
    global total,bound
    st[i][j]=True
    total+=1
    for direction in directions:
        x = i+direction[0]
        y = j +direction[1]
        if x>=1 and x<=n and y>=1 and y<=n and g[x][y]=='.':
            bound +=1
            break
    for direction in directions:
        x = i+direction[0]
        y = j +direction[1]
        if x>=1 and x<=n and y>=1 and y<=n and g[x][y]=='#' and not st[x][y]:
            dfs(x,y)
    
res = 0         
for i in range(1,1+n):
    for j in range(1,1+n):
        if g[i][j]=='#' and not st[i][j]:
            global total
            global bound
            total,bound =0,0
            dfs(i,j)
            if total == bound:
                res += 1
        
print(res)

鹅鹅鹅
为啥bfs也爆栈了

from collections import deque
q = deque()
n = int(input())
g = [[0]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    g[i][1:] = list(input())
st = [[False]*(n+1) for _ in range(n+1)]
directions = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs(i,j):
    global total,bound
    while q:
        flag = False
        t = q.popleft()
        st[t[0]][t[1]] = True
        total +=1
        for direction in directions:
            x = t[0]+direction[0]
            y = t[1]+direction[1]
            if x>=1 and x<=n and y>=1 and y<=n:
                if not flag and g[x][y]=='.':
                    flag = True
                    bound +=1
                if not st[x][y] and g[x][y]=='#':
                    q.append([x,y])
        
    
res = 0         
for i in range(1,1+n):
    for j in range(1,1+n):
        if g[i][j]=='#' and not st[i][j]:
            global total
            global bound
            total,bound =0,0
            q.append([i,j])
            bfs(i,j)
            if total == bound:
                res += 1
        
print(res)

我感觉我的代码没问题，主要是文件读入的问题

1240

是简单的代码，但是还是写出了问题
1、首先，需要注意数据的取值范围，有可能取负数，所以maxn初始化=-1不合适。

2、更新maxn的值，赋值别写反了
3、这题考查双指针，主要体现在，i代表每层的第一个数的位置，也就是1,2，4,8；而j代表的是从i开始遍历每层。

每层的长度是2**（d-1）
数组a下标从1开始。

4、这里面另一个需要注意的点就是，完全二叉树的最后一行，并不一定是满的——最后一行在遍历的时候可能会导致a出界。

这个时候需要用min()来限制最后一行遍历的坐标，也就是min（整体的数量对应下标+1，每一行对应最后一位下标+1）。

当为最后一行时，如果不满，则取前者；如果不为最后一行，则取后者。

n = int(input())
a = [0] + list(map(int,input().split()))
d,i=1,1
# 因为a的值可能很小，所以实际上maxn为-1可能并不会被更新
maxn =-float('inf') 
res = 0
while i<=n+1:
    s = 0
    for j in range(i,min(i+2**(d-1),n+1)):
        s += a[j]
    if s>maxn:
        # 别写反了，很简单的代码
        maxn =s
        res = d
    i *=2
    d +=1
print(res)

现在10：33了，下午需要提前上课，先去吃饭了！！！加油！

下了课好累啊，在床上瘫了好久。

看了好久的视频，一不小心山楂条又吃多了，下次要克制住啊！！！

现在来测试一下python和蓝桥杯地oj。

好卡顿的网站，好难用的oj。

ok。

那总结一下我们都学了什么吧！！！
先这样啦~我要翻之前的帖子了！