盛日辉的博客
0%

蓝桥-全球变暖

发表于 分类于 ， ，

题目

https://www.lanqiao.cn/problems/178/learning/

DFS

会栈溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 05-全球变暖1
import sys

sys.setrecursionlimit(600000)


def dfs(i, j):
    global flag, vis, mp, Dir
    if mp[i + 1][j] == "#" and mp[i - 1][j] == "#" and \
            mp[i][j + 1] == "#" and mp[i][j - 1] == "#":
        flag = True
        # return
    for di, dj in Dir:
        ni, nj = i + di, j + dj
        # if ni < 0 or nj < 0 or ni >= n or nj >= n or vis[ni][nj]:
        #     continue
        # 因为最外面一圈都是海
        if not vis[ni][nj] and mp[ni][nj] == "#":
            vis[ni][nj] = True
            dfs(ni, nj)
            # vis[ni][nj] = False


ans = 0
n = int(input())
mp = []
vis = [[False] * n for _ in range(n)]
Dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(n):
    mp.append(list(input()))
for x in range(n):
    for y in range(n):
        if mp[x][y] == "." or vis[x][y]:
            continue
        # print(x,y)
        flag = False
        vis[x][y] = True
        dfs(x, y)
        if not flag:
            ans += 1
print(ans)

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
# 02-全球变暖-1
from collections import deque


def bfs(i, j):
    global flag
    q = deque()
    q.append((i, j))
    vis[i][j] = True
    while q:
        x, y = q.popleft()
        if mp[x + 1][y] == "#" and mp[x - 1][y] == "#" and \
                mp[x][y + 1] == "#" and mp[x][y - 1] == "#":
            flag = True
        for dx, dy in Dir:
            nx, ny = x + dx, y + dy
            if not vis[nx][ny] and mp[nx][ny] == "#":
                vis[nx][ny] = True
                q.append((nx, ny))


ans = 0
n = int(input())
mp = []
vis = [[False] * n for _ in range(n)]
Dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(n):
    mp.append(list(input()))
for x in range(n):
    for y in range(n):
        if mp[x][y] == "." or vis[x][y]:
            continue
        # print(x,y)
        flag = False
        vis[x][y] = True
        bfs(x, y)
        if not flag:
            ans += 1
print(ans)
"""
输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......
copy
输出

1

10
 .......... .......... ...#...... .......... ....#.##.. ....#.##.. .#..####.. .#........ .##....... ..........
"""

"""
20
....................
....................
....................
....................
....#...............
....########........
....##########......
....###############.
.....##############.
.....##############.
.....##############.
......#############.
......#############.
......#############.
.......############.
.......############.
........###########.
.........##########.
..........#########.
....................

"""