编程模板!!!!!
利用编程模板快速把必要的步骤完成.代码的分治.
//写一个编程模板
#if 0
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
//输入参数变量
//存储输入变量
//自定义变量
//输入参数+存储输入变量
void init() {
}
//初始化自定义变量
void solveinit() {
}
//解决问题
void solve() {
solveinit();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//如果没有多个用例
init();
solve();
}
#endif // 1走出迷宫
链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。
障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；
小明想要知道，现在他能否从起点走到终点。
输入描述:
本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行，每行M个字符，表示地图的状态。
数据范围：
2<=N,M<=500
保证有一个起点S，同时保证有一个终点E.
输出描述:
每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No
示例1
输入
复制3 3 S.. ..E ... 3 3 S## ### ##E
3 3
S..
..E
...
3 3
S##
###
##E
输出
复制Yes No
Yes
No
1.
对于一个测试用例,输入参数有n,m以及n,m对应的迷宫图.
init函数的作用是将一个单位的测试用例数据全部用变量存储起来.
2.
solve函数的作用是完成一个单位的测试用例的解题工作.
solve函数之前进行solveinit函数.
将我们自定义变量进行初始化工作.
然后用solve进行解题.
3.
如果有多个测试用例,在main函数中控制多个测试用例.
4.
visited记录所有位置是否已经访问过,不需要回溯,如果回溯操作会导致大量路径重复计算,此时会导致超时.
所以切记不可回溯.
5.
dfs中返回值表示是否找到唯一路径,dfs返回值的应用,如果找到了唯一路径,返回true,一路飞升.
如果找到了就返回true,dfs返回值是true,直接返回true,不需要做其他任何操作.一路返回到头.
6.
把墙的位置的visited记录为true,统一判断条件,只需要判断visited是否为false,表示该位置是否可以进入.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
int dx[] = { 1,-1,0,0 }; // 定义x方向上的移动数组
int dy[] = { 0,0,1,-1 }; // 定义y方向上的移动数组
// 输入参数变量
ll n, m;
// 存储输入变量
vector<vector<char>> g; // 存储迷宫地图
// 自定义变量
p start_; // 起点坐标
p end_; // 终点坐标
vector<vector<ll>> visited; // 记录访问过的位置
// 输入参数+存储输入变量
void init() {
g.clear();
g.resize(n, vector<char>(m)); // 调整地图大小
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j]; // 读取地图信息
}
}
}
// 初始化自定义变量
void solveinit() {
visited.clear();
visited.resize(n, vector<ll>(m)); // 调整访问记录数组大小
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 'S') { // 如果是起点
start_ = { i,j }; // 记录起点坐标
}
if (g[i][j] == 'E') { // 如果是终点
end_ = { i,j }; // 记录终点坐标
}
if (g[i][j] == '#') { // 如果是障碍物
visited[i][j] = true; // 记录为已访问
}
}
}
}
int dfs(int i, int j) {
visited[i][j] = true; // 标记当前位置为已访问
if (end_ == (p){i, j}) { // 如果当前位置是终点
return true; // 返回可以到达
}
for (int k = 0; k < 4; k++) { // 遍历四个方向
int x = i + dx[k]; // 计算下一步的x坐标
int y = j + dy[k]; // 计算下一步的y坐标
if (x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]) { // 如果下一步位置合法且未访问过
if(dfs(x, y)) return true; // 递归进行下一步搜索，如果找到可达终点的路径，则返回true
}
}
//visited[i][j] = false; // 回溯，恢复当前位置为未访问状态
return false; // 如果四个方向都无法到达终点，则返回false
}
// 解决问题
void solve() {
solveinit(); // 初始化
if (dfs(start_.first, start_.second)) cout << "Yes" << endl; // 如果从起点出发能到达终点，则输出Yes
else cout << "No" << endl; // 否则输出No
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// 如果没有多个用例
while (cin >> n >> m) { // 输入迷宫的行数和列数
init(); // 初始化地图
solve(); // 解决问题
}
}
石油采集
链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇油行业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。
地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水
输入描述:
测试输入包含多条测试数据
测试数据的第一行给出了测试数据的数目T（T<75）
每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。
输出描述:
输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。
示例1
输入
复制1 6 ...... .##... ...... .#..#. .#..## ......
1
6
......
.##...
......
.#..#.
.#..##
......
输出
复制Case 1: 3
Case 1: 3
1.
需要查找每一个连通的油区有多少个1x2的矩形,计算一个连通区域奇数偶数的油田个数,此时奇数偶数中较小的一个就是此时最多的矩形个数.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
int dx[] = { 1,-1,0,0 }; // 定义x方向上的移动数组
int dy[] = { 0,0,1,-1 }; // 定义y方向上的移动数组
// 输入参数变量
int t, n; // 测试用例数量t，地图大小n
// 存储输入变量
vector<vector<char>> g; // 存储地图信息
// 自定义变量
vector<vector<bool>> visited; // 记录是否访问过
ll even, old; // 记录偶数和奇数数量
ll ret; // 结果
ll index_ = 1; // 记录当前测试用例编号
// 输入参数+存储输入变量
void init() {
cin >> n; // 读取地图大小
g.clear();
g.resize(n, vector<char>(n)); // 调整地图大小
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j]; // 读取地图信息
}
}
}
// 初始化自定义变量
void solveinit() {
ret = 0;
visited.clear();
visited.resize(n, vector<bool>(n)); // 调整访问记录数组大小
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '.') visited[i][j] = true; // 如果是海面，则标记为已访问
}
}
}
// 深度优先搜索
void dfs(int i, int j) {
visited[i][j] = true; // 标记当前位置为已访问
if (((i + j) & 1) == 0) even++; // 如果当前位置的行列坐标和为偶数，则偶数数量加一
else old++; // 否则奇数数量加一
for (int k = 0; k < 4; k++) { // 遍历四个方向
int x = i + dx[k]; // 计算下一步的x坐标
int y = j + dy[k]; // 计算下一步的y坐标
if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y]) { // 如果下一步位置合法且未访问过
dfs(x, y); // 递归进行下一步搜索
}
}
}
// 解决问题
void solve() {
solveinit(); // 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
even = 0, old = 0; // 初始化偶数和奇数数量
if (!visited[i][j]) dfs(i, j); // 如果当前位置未访问过，则进行深度优先搜索
ret += min(old, even); // 更新结果
}
}
cout << "Case " << index_++ << ": " << ret << endl; // 输出结果
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// 如果没有多个用例
cin >> t; // 读取测试用例数量
while (t--) { // 循环处理每个测试用例
init(); // 初始化
solve(); // 解决问题
}
}
after与迷宫
链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
after的算法书的遗落在一个叫做AIJ的迷宫中了，这个迷宫有N*M个房间，迷宫的入口为(1，1)，算法书遗落在(r，c)。迷宫中的房间有四种状态：空房间、无法进入的房间、有墨菲斯托存在的房间和有莉莉丝存在的房间。墨菲斯托会否定一切，而莉莉丝会诱惑人做一种叫做YK的活动。after是一个意志薄弱的人，他遇到了墨菲斯托和莉莉丝之后，便会变成眼神空洞的超级YK机器人。after每步可以从他当前的房间走至上下左右四个房间的其中一个房间。after害怕变成超级YK机器人，所以要尽快拿到算法书然后从入口逃离。问after最少需要走多少步才可以在不变成超级YK机器人的情况下从入口出发取回算法书并逃离迷宫？
输入描述:
第一行一个正整数T(T<=10)，表示共有T组数据。
对于每组数据，第一行四个正整数N，M，r，c(1<=N,M<=1000；1<=r<=N；1<=c<=M)。
接下来N行，每行M个字符，每个表示房间的状态，“.”表示空房间，“*”表示无法进入的房间，“F”表示有墨菲斯托存在的房间，“M”表示有莉莉丝存在的房间。
数据保证(1，1)为“.”。
输出描述:
对每组数据输出一行，即after最少需要走的步数。若after无法取回算法书，则输出“IMPOSSIBLE”(不带引号)。
示例1
输入
复制1 4 4 4 3 ..** *F.. *.*. *M.F
1
4 4 4 3
..**
*F..
..
*M.F
输出
复制14
14
1.
不能同时遇到F和M,也就是说只能遇到M或者遇到F,只需要将F当作是路,或者将M当作是路即可.
2.
BFS用一张表记录各个位置到某一个位置的最短路径,BFS第一次进入一个节点此时就是以最短路径进入节点.
结合了一点点动态规划,当前位置的最短路径是上一个节点最短路径+1.
3.
BFS维护信息在上一节点维护,此时的优势是可以利用上一节点的信息.
4.
BFS利用队列实现广度优先遍历,队列存储左边,利用piar表示坐标.
5.
注意题目下标是从1开始也就是1-based,我们通常都是0-based,所以对应数据要--操作.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
ll dx[] = { 1,-1,0,0 }; // 定义x方向上的移动数组
ll dy[] = { 0,0,1,-1 }; // 定义y方向上的移动数组
// 输入参数变量
ll t, n, m, r, c; // 测试用例数量t，迷宫大小n和m，算法书遗落位置r和c
// 存储输入变量
vector<vector<char>> g; // 存储迷宫信息
// 自定义变量
vector<vector<ll>> dis; // 存储距离信息
// 输入参数+存储输入变量
void init() {
cin >> n >> m >> r >> c; // 读取迷宫大小和算法书遗落位置
r--, c--; // 将位置转换为0-based索引
g.clear();
g.resize(n, vector<char>(m)); // 调整迷宫大小
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j]; // 读取迷宫信息
}
}
}
// 初始化自定义变量
void solveinit() {
dis.clear();
dis.resize(n, vector<ll>(m, LLONG_MAX)); // 初始化距离数组为最大值
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '*') dis[i][j] = -1; // 如果是无法进入的房间，则距离设为-1
}
}
}
// BFS初始化
void bfsinit() {
dis.clear();
dis.resize(n, vector<ll>(m, LLONG_MAX)); // 初始化距离数组为最大值
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '*') dis[i][j] = -1; // 如果是无法进入的房间，则距离设为-1
}
}
}
// BFS算法
ll bfs(char it) {
bfsinit(); // 初始化
queue<p> q;
q.push({ 0,0 }); // 将起点入队
dis[0][0] = 0; // 起点距离设为0
while (!q.empty()) {
auto top = q.front();
q.pop();
ll i = top.first;
ll j = top.second;
if (i == r && j == c) return dis[i][j]; // 如果到达目标位置，则返回距离
for (int k = 0; k < 4; k++) {
ll x = i + dx[k]; // 计算下一步的x坐标
ll y = j + dy[k]; // 计算下一步的y坐标
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != it && dis[x][y] == LLONG_MAX) { // 如果下一步位置合法且未访问过且不是目标房间
q.push({ x,y }); // 将下一步位置入队
dis[x][y] = dis[i][j] + 1; // 更新距离
}
}
}
return LLONG_MAX; // 如果无法到达目标位置，则返回最大值
}
// 解决问题
void solve() {
solveinit(); // 初始化
ll ret = bfs('M'); // 从莉莉丝的房间出发
ret = min(ret, bfs('F')); // 比较从墨菲斯托的房间出发和从莉莉丝的房间出发的距离
if (ret == LLONG_MAX) cout << "IMPOSSIBLE" << endl; // 如果无法取回算法书，则输出"IMPOSSIBLE"
else cout << 2 * ret << endl; // 否则输出最小步数的两倍，因为一步是到达目标房间，另一步是返回入口
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// 如果没有多个用例
cin >> t; // 读取测试用例数量
while (t--) { // 循环处理每个测试用例
init(); // 初始化
solve(); // 解决问题
}
}
逃离迷宫
链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
给你一个n*m的图，地图上'.'代表可以走的地方，而'#'代表陷阱不能走，
'P'代表人物位置，'K'代表钥匙，'E'代表出口。人物一个，钥匙有多个，
（'K'的数量<=50)）,出口一个，每个位置可以向（上，下，左，右）四个
方向走一格，花费一个单位时间，现在你需要花费最少的时间拿到钥匙
然后从迷宫的出口出去(若没有钥匙，则不能进入迷宫出口所在的格子)。
输入描述:
第一行一个整数T(T <= 50)，代表数据的组数
接下来一行n,m(n<=500,m<=500),代表地图的行和列
接下来n行，每行一个长度为m的字符串，组成一个图。
输出描述:
如果可以出去，输出所花费的最少时间。
如果不能出去，输出一行"No solution"。
示例1
输入
复制3 5 5 ....P ##..E K#... ##... ..... 5 5 P.... ..... ..E.. ..... ....K 5 5 P#..E .#.#. .#.#. .#.#. ...#K
3
5 5
....P
##..E
K#...
##...
.....
5 5
P....
.....
..E..
.....
....K
5 5
P#..E
.#.#.
.#.#.
.#.#.
...#K
输出
复制No solution 12 No solution
No solution
12
No solution
1.
只需要用两次BFS即可,用两次BFS分别填写好两张表,第一张表是记录所有位置到路口位置的最短路径,另一张表是记录所有位置到出口的最短路径,只需要遍历所有钥匙位置,然后查找该位置到入口最短路径和到出口最短路径,加起来就是总最短路径.找到所有钥匙位置的总最短路径即可.
2.
因为要填写两张表,所以BFS接受两个参数,表示入口位置和需要填写的表是什么.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
//输入参数变量
int t, n, m; // 测试用例数，地图的行数和列数
//存储输入变量
vector<string>g; // 存储地图信息
//自定义变量
vector<vector<ll>> dis_start; // 从起点到各个点的距离
vector<vector<ll>> dis_end; // 从终点到各个点的距离
p __start; // 起点的坐标
p __end; // 终点的坐标
vector<p> _point; // 存储钥匙的位置
//输入参数+存储输入变量
void init() {
cin >> n >> m; // 读入地图的行数和列数
g.clear(); // 清空地图信息
string tmp;
for (int i = 0; i < n; i++) {
cin >> tmp; // 读入地图的每一行
g.push_back(tmp); // 将地图的每一行存入g中
}
}
//初始化自定义变量
void solveinit() {
dis_start.clear(); // 清空起点到各个点的距离
dis_end.clear(); // 清空终点到各个点的距离
_point.clear(); // 清空钥匙的位置
dis_start.resize(n, vector<ll>(m, LLONG_MAX)); // 初始化起点到各个点的距离为最大值
dis_end.resize(n, vector<ll>(m, LLONG_MAX)); // 初始化终点到各个点的距离为最大值
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '#') { // 如果当前位置是陷阱
dis_start[i][j] = -1; // 起点到该位置的距离设为-1
dis_end[i][j] = -1; // 终点到该位置的距离设为-1
}
if (g[i][j] == 'P') __start = { i,j }; // 如果当前位置是起点，则记录起点坐标
if (g[i][j] == 'E') __end = { i,j }; // 如果当前位置是终点，则记录终点坐标
if (g[i][j] == 'K') _point.push_back({ i,j }); // 如果当前位置是钥匙，则记录钥匙的坐标
}
}
}
// 广度优先搜索计算起点到各个点的距离
void bfs(p& point_, vector<vector<ll>>& dis_) {
queue<p> q;
q.push(point_); // 将起点入队列
dis_[point_.first][point_.second] = 0; // 起点到自身的距离为0
while (!q.empty()) {
auto top = q.front(); // 取出队首元素
q.pop(); // 弹出队首元素
int i = top.first;
int j = top.second;
if (point_ == __start && i == __end.first && j == __end.second) continue; // 如果当前是起点并且到达了终点，则继续下一次循环
for (int k = 0; k < 4; k++) { // 遍历上下左右四个方向
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m && dis_[x][y] == LLONG_MAX) { // 如果新位置在地图范围内且未被访问过
q.push({ x,y }); // 将新位置入队列
dis_[x][y] = dis_[i][j] + 1; // 更新新位置的距离为当前位置的距离加1
}
}
}
}
//解决问题
void solve() {
solveinit(); // 初始化自定义变量
bfs(__start, dis_start); // 计算起点到各个点的距离
bfs(__end, dis_end); // 计算终点到各个点的距离
ll ret = LLONG_MAX; // 初始化最小花费时间为最大值
for (auto& x : _point) {
int i = x.first;
int j = x.second;
ll d1 = dis_start[i][j]; // 获取起点到钥匙的距离
ll d2 = dis_end[i][j]; // 获取终点到钥匙的距离
if (d1 == LLONG_MAX || d2 == LLONG_MAX) continue; // 如果起点到钥匙或者终点到钥匙的距离为最大值，说明无法到达该钥匙或者无法到达终点，跳过该钥匙
ret = min(d1 + d2, ret); // 更新最小花费时间
}
if (ret == LLONG_MAX)cout << "No solution" << endl; // 如果最小花费时间仍然为最大值，说明无法到达终点，输出"No solution"
else cout << ret << endl; // 否则输出最小花费时间
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//如果没有多个用例
cin >> t; // 读入测试用例数
while (t--) {
init(); // 初始化输入参数变量和存储输入变量
solve(); // 解决问题
}
}
结论
1.
编程模板可以使代码非常的清晰,也可以让我们完成必要的工作而不去思考问题本身.
必要的工作部分专心完成必要工作即可.
分区分块解题步骤.
2.
BFS存储各个位置到某个位置的最短路径.单源
多源可以存储各个位置到同地位的位置的最短路径.
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
