题一

难度:普及-

https://www.luogu.com.cn/problem/P1331

题目背景

在峰会期间，武装部队得处于高度戒备。警察将监视每一条大街，军队将保卫建筑物，领空将布满了 F-2003 飞机。

此外，巡洋船只和舰队将被派去保护海岸线。不幸的是，因为种种原因，国防海军部仅有很少的几位军官能指挥大型海战。因此，他们培养了一些新海军指挥官。军官们选择了“海战”游戏来帮助他们学习。

题目描述

在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能碰到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形组成的方形。

求出该棋盘上放置的船只的总数。

输入格式

第一行为两个整数 RR 和 CC，用空格隔开，分别表示游戏棋盘的行数和列数。

接下来 RR 行，每行 CC 个字符，为 # 或 .。# 表示船只的一部分，. 表示水。

输出格式

一行一个字符串，如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个 # 号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出 There are S ships.，SS 表示船只的数量。否则输出 Bad placement.。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#

输出 #1

1
2
There are 5 ships.

说明/提示

对于 100%100\% 的数据，1≤R,C≤10001 \le R,C \le 1000。

解题思路

不同于常规的单次对全部数据bfs,这题需要对所有相互不连通的#区域单独bfs
定义bfs函数并返回一个布尔值,该布尔值表示这段连通的#是否是一搜合法的船
如何高效的判断一段连通的#是否为一个标准的矩形呢,一次简单的计算即可:

1
最长 * 最宽 == #总数

完整代码实现

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
import sys
from collections import deque
from array import array

r, c = map(int, input().split())
grid = []
for _ in range(r):
    row = list(sys.stdin.readline().strip())
    grid.append(row)
visited = [[False] * c for _ in range(r)]
dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
count = 0

def bfs(begin):
    q = deque()
    visx = array("i", [])
    visy = array("i", [])
    cnt = 1
    q.append(begin)
    while q:
        x, y = q.popleft()
        visx.append(x)
        visy.append(y)
        visited[x][y] = True
        for dx, dy in dire:
            if 0 <= x + dx < r and 0 <= y + dy < c and not visited[x + dx][y + dy] and grid[x+dx][y+dy] == '#':
                q.append((x + dx, y + dy))
                visited[x + dx][y + dy] = True
                visx.append(x + dx)
                visy.append(y + dy)
                cnt += 1
    return cnt == (max(visx) - min(visx) + 1) * (max(visy) - min(visy) + 1)  #判断是不是标准矩形

for i in range(r):
    for j in range(c):
        if grid[i][j] == '#' and not visited[i][j]:  #寻找未被访问的#区域
            if not bfs((i, j)):
                print("Bad placement.")
                sys.exit()  #非标准矩形直接退出
            count += 1
print(f"There are {count} ships.")

题二

难度:普及/提高-

https://www.luogu.com.cn/problem/P1135

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 ii 层楼（1≤i≤N1 \le i \le N）上有一个数字 KiK_i（0≤Ki≤N0 \le K_i \le N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3,3,1,2,53, 3, 1, 2, 5 代表了 KiK_i（K1=3K_1=3，K2=3K_2=3，……），从 11 楼开始。在 11 楼，按“上”可以到 44 楼，按“下”是不起作用的，因为没有 −2-2 楼。那么，从 AA 楼到 BB 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 N,A,BN, A, B（1≤N≤2001 \le N \le 200，1≤A,B≤N1 \le A, B \le N）。

第二行为 NN 个用空格隔开的非负整数，表示 KiK_i。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

输入输出样例 #1

输入 #1

1
2
5 1 5
3 3 1 2 5

输出 #1

1
3

说明/提示

对于 100%100 \% 的数据，1≤N≤2001 \le N \le 200，1≤A,B≤N1 \le A, B \le N，0≤Ki≤N0 \le K_i \le N。

本题共 1616 个测试点，前 1515 个每个测试点 66 分，最后一个测试点 1010 分。

解题思路

这题也是比较简单,常规搜法,2个方向,加一个越界判断即可

完整代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque
import sys

n,a,b =  map(int,sys.stdin.readline().strip().split())
data = list(map(int,sys.stdin.readline().strip().split()))
q = deque([(a,0)])
visited = [False]*(n+1)
visited[a] = True
dires = [1,-1]
if a == b:
    print(0)
    sys.exit()
while q:
    pos,step = q.popleft()
    for dir in dires:
        if 1 <= pos + data[pos-1]*dir <= n and pos + data[pos-1]*dir != b and not visited[pos + data[pos-1]*dir]:
            visited[pos + data[pos-1]*dir] = True
            q.append((pos + data[pos-1]*dir,step+1))
        elif pos + data[pos-1]*dir == b:
            print(step+1)
            sys.exit()
print(-1)

题三

难度:普及+/提高

https://www.luogu.com.cn/problem/P1126

题目描述

机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径 1.61.6 米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个 N×MN\times M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：

  • 向前移动 11 步（Creep）；
  • 向前移动 22 步（Walk）；
  • 向前移动 33 步（Run）；
  • 向左转（Left）；
  • 向右转（Right）。

每个指令所需要的时间为 11 秒。请你计算一下机器人完成任务所需的最少时间。

输入格式

第一行为两个正整数 N,M (1≤N,M≤50)N,M\ (1\le N,M\le50)，下面 NN 行是储藏室的构造，00 表示无障碍，11 表示有障碍，数字之间用一个空格隔开。接着一行有 44 个整数和 11 个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东 E\tt E，南 S\tt S，西 W\tt W，北 N\tt N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出 −1-1。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

输出 #1

1
12

解题思路

这题有一些坑点:

  • 障碍物在方格内,而机器人是行走在网格线上的,这意味着一个方格的障碍物会导致方格的4个定点都不可到达
  • 机器人是直径1.6的圆形,这意味着机器人的实际占用空间是4个方格

技巧:

  • 预处理valid数组,记录所有机器人可以走的格点坐标(排除网格边界和障碍)
  • 方向整数化:机器人面朝方向以字符串输入,不易操作,可将其转化为0~3的整数
  • visited需要设定为三维数组,不仅记录机器人的位置坐标,还要记录其面朝方向
  • 队列中记录4个信息:坐标x,y,面朝方向,当前步数

完整代码实现

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
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().strip().split())
visited = [[False] * m for _ in range(n)]
grid = []
for _ in range(n):
    row = list(map(int, sys.stdin.readline().strip().split()))
    grid.append(row)
bx, by, ex, ey, dir = sys.stdin.readline().strip().split()
if dir == 'S':
    dir = 0
elif dir == 'W':
    dir = 1
elif dir == 'N':
    dir = 2
elif dir == 'E':
    dir = 3
bx, by, ex, ey = map(int, (bx, by, ex, ey))

valid = [[True] * (m + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(m):
        if grid[i][j] == 1: #障碍处不可达
            valid[i][j] = False
            valid[i + 1][j] = False
            valid[i][j + 1] = False
            valid[i + 1][j + 1] = False
for i in range(n + 1):  #边界不可达
    valid[i][0] = valid[i][m] = False
for i in range(m + 1):
    valid[0][i] = valid[n][i] = False

q = deque([(bx, by, dir, 0)])
visited = [[[False] * 4 for _ in range(m + 1)] for _ in range(n + 1)]
visited[bx][by][dir] = True

while q:
    x, y, direc, step = q.popleft()
    if x == ex and y == ey:
        print(step)
        sys.exit()

    for ste in range(1, 4):
        if direc == 0:
            if 0 <= x + ste <= n and valid[x + ste][y]:
                if not visited[x + ste][y][direc]:
                    q.append((x + ste, y, direc, step + 1))
                    visited[x + ste][y][direc] = True
            else:
                break
        elif direc == 2:
            if 0 <= x - ste <= n and valid[x - ste][y]:
                if not visited[x - ste][y][direc]:
                    q.append((x - ste, y, direc, step + 1))
                    visited[x - ste][y][direc] = True
            else:
                break
        elif direc == 1:
            if 0 <= y - ste <= m and valid[x][y - ste]:
                if not visited[x][y - ste][direc]:
                    q.append((x, y - ste, direc, step + 1))
                    visited[x][y - ste][direc] = True
            else:
                break
        elif direc == 3:
            if 0 <= y + ste <= m and valid[x][y + ste]:
                if not visited[x][y + ste][direc]:
                    q.append((x, y + ste, direc, step + 1))
                    visited[x][y + ste][direc] = True
            else:
                break

    if not visited[x][y][(direc + 1) % 4]:
        q.append((x, y, (direc + 1) % 4, step + 1))
        visited[x][y][(direc + 1) % 4] = True
    if not visited[x][y][(direc - 1) % 4]:
        q.append((x, y, (direc - 1) % 4, step + 1))
        visited[x][y][(direc - 1) % 4] = True

print(-1)

不得不承认很高的重复度证明这是一坨屎山代码,但我认为这么写是容易理解的

题四

难度:普及+/提高

https://www.luogu.com.cn/problem/P1144

题目描述

给出一个 NN 个顶点 MM 条边的无向无权图，顶点编号为 1∼N1\sim N。问从顶点 11 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 22 个正整数 N,MN,M，为图的顶点数与边数。

接下来 MM 行，每行 22 个正整数 x,yx,y，表示有一条连接顶点 xx 和顶点 yy 的边，请注意可能有自环与重边。

输出格式

共 NN 行，每行一个非负整数，第 ii 行输出从顶点 11 到顶点 ii 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans mod 100003 ans \bmod 100003 后的结果即可。如果无法到达顶点 ii 则输出 00。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出 #1

1
2
3
4
5
6
1
1
1
2
4

说明/提示

11 到 55 的最短路有 44 条，分别为 22 条 1→2→4→51\to 2\to 4\to 5 和 22 条 1→3→4→51\to 3\to 4\to 5（由于 4→54\to 5 的边有 22 条）。

对于 20%20\% 的数据，1≤N≤1001\le N \le 100；
对于 60%60\% 的数据，1≤N≤1031\le N \le 10^3；
对于 100%100\% 的数据，1≤N≤1061\le N\le10^6，1≤M≤2×1061\le M\le 2\times 10^6。

解题思路

技巧:

  • 用代码表示节点到节点的连通:建立二维数组,每个子数组表示一个节点,子数组中存储的数字表示能与其连通的节点
  • dist数组存储节点1到某一节点最短路径的长度,初始化为INF,dist[1] = 0
  • ans数组存储最短路径的条数,初始化为0,ans[1] = 1

完整代码实现

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
import sys
from collections import deque

data = sys.stdin.read().strip().split()
idx = 0
n = int(data[idx])
idx += 1
m = int(data[idx])
idx += 1
graph = [[] for _ in range(n+1)]
INF = float("inf")
for _ in range(m):
    x = int(data[idx])
    idx += 1
    y = int(data[idx])
    idx += 1
    graph[x].append(y)
    graph[y].append(x)

dist = [INF]*(n+1)
dist[1] = 0
ans = [0]*(n+1)
ans[1] = 1
q = deque()
q.append(1)
while q:
    now = q.popleft()
    for i in graph[now]:
        if dist[i] == dist[now]+1:
            ans[i] = (ans[i] + ans[now]) % 100003
        elif dist[i] > dist[now]+1:
            dist[i] = dist[now]+1
            ans[i] = ans[now]
            q.append(i)
output = [str(ans[i]) for i in range(1, n+1)]
sys.stdout.write('\n'.join(output))

由于Python语言自身的局限性,面对这题的极端大数据时绝对会TLE,在洛谷提交时把语言改成PyPy3即可

晚上开始DFS喵~