问题解决策略搜索训练4

问题 A: 小鼠迷宫问题题目描述小鼠 aaa 与小鼠 bbb 身处一个 m×nm \times nm×n 的迷宫中如图所示。每一个方格表示迷宫中的一个房间。这 m×nm \times nm×n 个房间中有一些房间是封闭的不允许任何人进入。在迷宫中任何位置均可沿上下左右 444 个方向进入未封闭的房间。小鼠 aaa 位于迷宫的 (p,q)(p, q)(p,q) 方格中它必须找出一条通向小鼠 bbb 所在的 (r,s)(r, s)(r,s) 方格的路。请帮助小鼠 aaa 找出所有通向小鼠 bbb 的最短道路。请编程对于给定的小鼠的迷宫计算小鼠 aaa 通向小鼠 bbb 的所有最短道路。输入本题有多组输入数据你必须处理到EOF为止。 每组数据的第一行有 333 个正整数 n,m,kn, m, kn,m,k分别表示迷宫的行数列数和封闭的房间数。接下来的 kkk 行中每行 222 个正整数表示被封闭的房间所在的行号和列号。最后的 222 行每行也有 222 个正整数分别表示小鼠 aaa 所处的方格 (p,q)(p, q)(p,q) 和小鼠 bbb 所处的方格 (r,s)(r, s)(r,s)。输出对于每组数据将计算出的小鼠 aaa 通向小鼠 bbb 的最短路长度和有多少条不同的最短路输出。每组数据输出两行第一行是最短路长度第 222 行是不同的最短路数。每组输出之间没有空行。如果小鼠 aaa 无法通向小鼠 bbb 则输出No Solution!。输入输出样例样例输入 #1复制8 8 3 3 3 4 5 6 6 2 1 7 7样例输出 #1复制11 96这题先用bfs求出最短距离minn再用dfs统计长度等于minn的路径数量#includeiostream #includevector #includealgorithm #includequeue #includeunordered_map using namespace std; int sx, sy, ex, ey; int n, m, k; int cnt 0;//路径数量 int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; int minn 0x3f3f3f3f;//最短距离 struct edge { int x; int y; }; //暴力搜索所有可能的路径并统计长度等于minn的路径数量 void dfs(vectorvectorint g, vectorvectorbool vis, int x, int y, int cur) { //当前走过的步数cur已经超过了已知的最短路径minn就没必要继续搜了 if (cur minn) return; if (x ex y ey)//到了终点 { cnt;//找到一条路径计数器 1 return; } for (int i 0;i 4;i) { int nx x dx[i]; int ny y dy[i]; //判断新坐标是否在地图内且不是障碍物 if (nx 0 nx n ny 0 ny m g[nx][ny] 0) { vis[nx][ny] true;//标记访问 dfs(g, vis, nx, ny, cur 1); vis[nx][ny] false;//回溯 } } } int main() { while (cin n m k) { cnt 0;//重置计数器 minn 0x3f3f3f3f;//重置最短距离 vectorvectorintg(n, vectorint(m)); vectorvectorboolvis(n, vectorbool(m)); while (k--)// 读入障碍物 { int ox, oy; cin ox oy; g[ox][oy] 1; } cin sx sy ex ey; vectorvectorintdis(n, vectorint(m, 0x3f3f3f3f)); dis[sx][sy] 0;//起点到自己的距离是 0 queuestruct edgeq; q.push({ sx,sy });//把起点放入队列 while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0;i 4;i) { int nx t.x dx[i]; int ny t.y dy[i]; if (nx 0 nx n ny 0 ny m//判断新坐标是否合法 dis[t.x][t.y] 1 dis[nx][ny]//只有当新距离更小时才更新 g[nx][ny] 0)//且不是墙 { q.push({ nx,ny });//加入队列 dis[nx][ny] dis[t.x][t.y] 1;//更新最短距离 } } } minn dis[ex][ey];//从起点到终点的最短距离 if (minn 0x3f3f3f3f)//无法到达 cout No Solution!\n; else { cout minn \n;//最短距离 vis[sx][sy] true; dfs(g, vis, sx, sy, 0);//开始 DFS当前步数为 0 cout cnt \n;//路径数量 } } return 0; }当然这不是最优解。最优解是dfsdp为什么能在bfs里面加dpBFS 保证了顺序第一次访问某个点时一定是最短距离之后所有访问只可能是同层等长或更长如果我从cur走一步到nx,ny这条路的“总长度”正好等于nx,ny当前已知的最短路长度则到达nx,ny的最短路径数量就要“累加”从cur过来的路径数。状态转移方程$$dp[next]\left\{\begin{matrix} dis[cur]1dis[next]\\ dis[cur]1dis[next] \end{matrix}\right.$$#includeiostream #includevector #includealgorithm #includequeue #includeunordered_map using namespace std; int sx, sy, ex, ey; int n, m, k; int cnt 0;//路径数量 int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; int minn 0x3f3f3f3f;//最短距离 struct edge { int x; int y; }; int main() { while (cin n m k) { cnt 0;//重置计数器 minn 0x3f3f3f3f;//重置最短距离 vectorvectorintg(n, vectorint(m)); while (k--)// 读入障碍物 { int ox, oy; cin ox oy; g[ox][oy] 1; } cin sx sy ex ey; vectorvectorintdis(n, vectorint(m, 0x3f3f3f3f)); vectorvectorintdp(n, vectorint(m, 0x3f3f3f3f));//起点到(x, y)的最短路径数量 dp[sx][sy] 1;//起点只有 1 种走法 dis[sx][sy] 0;//起点到自己的距离是 0 queuestruct edgeq; q.push({ sx,sy });//把起点放入队列 while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0;i 4;i) { int nx t.x dx[i]; int ny t.y dy[i]; //新坐标越界或不可访问就跳过 if (nx 0 || nx n || ny 0 || ny m || g[nx][ny] 1) continue; if (dis[t.x][t.y] 1 dis[nx][ny])//只有当新距离更小时才更新 { q.push({ nx,ny });//加入队列 dis[nx][ny] dis[t.x][t.y] 1;//更新最短距离 dp[nx][ny] dp[t.x][t.y];//新最短路径重新计数 } else if (dis[nx][ny] dis[t.x][t.y] 1) dp[nx][ny] dp[t.x][t.y];//多条最短路径汇聚 } } minn dis[ex][ey];//从起点到终点的最短距离 cnt dp[ex][ey]; if (minn 0x3f3f3f3f)//无法到达 cout No Solution!\n; else { cout minn \n;//最短距离 cout cnt \n;//路径数 } } return 0; }问题 B: Hero In Maze题目描述500 年前Jesse 是我国最卓越的剑客。他英俊潇洒而且机智过人 ^_^。突然有一天Jesse 心爱的公主被魔王困在了一个巨大的迷宫中。Jesse 听说这个消息已经是两天以后了他知道公主在迷宫中还能坚持 TTT 天他急忙赶到迷宫开始到处寻找公主的下落。 时间一点一点的过去Jesse 还是无法找到公主。最后当他找到公主的时候美丽的公主已经死了。从此 Jesse 郁郁寡欢茶饭不思一年后追随公主而去了。T_T500 年后的今天Jesse 托梦给你希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。他会为你提供迷宫的地图以及所剩的时间 TTT。请你判断他是否能救出心爱的公主。输入题目包括多组测试数据。每组测试数据以三个整数 N,M,TN, M, TN,M,T0n,m≤20;t00 \lt n, m \le 20; t \gt 00n,m≤20;t0开头分别代表迷宫的长和高以及公主能坚持的天数。紧接着有 MMM 行NNN 列字符由.*PS组成。其中.代表能够行走的空地。*代表墙壁Jesse 不能从此通过。P是公主所在的位置。S是 Jesse 的起始位置。每个时间段里 Jesse 只能选择“上、下、左、右”任意一方向走一步。输入以0 0 0结束。输出如果能在规定时间内救出公主输出YES否则输出NO。输入输出样例样例输入 #1复制4 4 10 .... .... .... S**P 0 0 0样例输出 #1复制YES提示报告参见 http://acm.zjgsu.edu.cn/Report/1005/1005.html。这题用bfs。#includeiostream #includevector #includequeue using namespace std; int m, n, t; int sx, sy, ex, ey; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; struct node { int x; int y; }; int main() { while (cin m n t m ! 0 n ! 0 t ! 0) { vectorvectorintg(n, vectorint(m)); for (int i 0;i n;i) { for (int j 0;j m;j) { char ch; cin ch; if (ch S)//剑客 { sx i; sy j; } if (ch P)//公主 { ex i; ey j; } if (ch *)//墙壁 g[i][j] 1; } } queuestruct nodeq; vectorvectorintdis(n, vectorint(m, 0x3f3f3f3f)); dis[sx][sy] 0;//起点到自己的距离为0 q.push({ sx,sy }); while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0;i 4;i) { int nx t.x dx[i]; int ny t.y dy[i]; //不越界、不是墙、新路径更短 if (nx 0 nx n ny 0 ny m g[nx][ny] 0 dis[t.x][t.y] 1 dis[nx][ny]) { dis[nx][ny] dis[t.x][t.y] 1;//更新最小距离 q.push({ nx,ny });//加入队列 } } } //如果最短步数 ≤ 允许时间 if (dis[ex][ey] t) cout YES\n; else cout NO\n; } return 0; }问题 C: 泊松分酒题目描述泊松是法国数学家、物理学家和力学家。他一生致力科学事业成果颇多。有许多著名的公式定理以他的名字命名比如概率论中著名的泊松分布。有一次闲暇时他提出过一个有趣的问题后称为“泊松分酒”。在我国古代也提出过类似问题遗憾的是没有进行彻底探索其中流传较多是“韩信走马分油”问题。有 333 个容器容量分别为 121212 升888 升555 升。其中 121212 升中装满油另外两个空着。要求你只用 333 个容器操作最后使得某个容器中正好有 666 升油。下面的列表是可能的操作状态记录12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5每行 333 个数据分别表示 12,8,612, 8, 612,8,6 升容器中的油量第一行表示初始状态第二行表示把 121212 升倒入 888 升容器后的状态第三行是 888 升倒入 555 升...当然同一个题目可能有多种不同的正确操作步骤。输入输入各个容器的容量开始的状态和要求的目标油量输入保证只有三个容器输入保证按照容器的容量大小按照降序给出保证所有数据都不会超过100输出程序通过计算输出一种实现的步骤不需要找到所有可能的方法。如果没有可能实现则输出不可能。输入输出样例样例输入 #1复制12,8,5,12,0,0,6样例输出 #1复制12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5问题 D: 共享单车题目描述共享单车走进烟台小明决定尝试。小明启动共享单车 App轻松地找到附近的单车。那么问题来了到最近的那辆单车小明大约要走多少米呢现在简化问题。将地图设定成一个由 100×100100 \times 100100×100 米的像素块组成的二维平面区域。如果一个方块内有单车则像素块显示为字符x如果此方块内是可以通行的路则显示为.再如果方块是建筑物则显示为*建筑物不能通行。小明在地图上的位置显示为o可以朝“上”、“下”、“左”“右”“左上”“左下”“右上”“右下”八个方向走。下图所示为一个小明站在像素方块O如果小明向右走到X则走 100100100 米如果向右上走则走 141141141 米不需要开方。假设小明和单车都在方块的中央。现在给出 TTT 幅根据以上规则建立的地图地图行数和列数分别为 nnn 和 mmm请分别估算小明要走多少米才能到最近的单车给出的地图中至少有一辆单车如果最终无法到达单车的位置输出-1。输入第 111 行 TTT表示下面有 TTT 组测试数据对于每组测试数据第 111 行 nnn 和 mmm表示地图的大小第 222 行开始给出具体的地图 。输出TTT 行数据每行 111 个整数表示问题的解输入输出样例样例输入 #1复制2 3 8 .....x.. .o...x.. ........ 8 10 .***...... .***...... .***..x... .......... .....***** ..o..***** .......x.. ...*******样例输出 #1复制400 523提示如果计算中出现小数那么直接舍弃。最后的输出的结果为整型。这题求最短路而且边权不固定所以用bfsDijkstra最短路算法。#includeiostream #includevector #includealgorithm #includequeue #define int long long using namespace std; struct edge { int x; int y; int val; bool operator(const struct edge other) const { return val other.val; } }; //拆成两组是为了分别加不同的权重 int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; int dx2[4] { 1,1,-1,-1 }; int dy2[4] { 1,-1,1,-1 }; int sx, sy; signed main() { int t; cin t; while (t--) { int n, m; cin n m; vectorvectorintg(n, vectorint(m)); for (int i 0;i n;i) { for (int j 0;j m;j) { char ch; cin ch; if (ch *)//建筑 g[i][j] -1; if (ch x)//单车 g[i][j] 1; if (ch o)//起点 { sx i; sy j; } } } vectorvectorintdis(n, vectorint(m, 0x3f3f3f3f)); priority_queuestruct edge, vectorstruct edge, greaterstruct edgeq; q.push({ sx,sy,0 }); dis[sx][sy] 0; int ret 0x3f3f3f3f; while (!q.empty()) { auto t q.top(); q.pop(); if (t.val dis[t.x][t.y]) continue; //cout t.x t.y t.val \n; if (g[t.x][t.y] 1)//找到目标就结束 { ret t.val; break; } //正交方向 for (int i 0;i 4;i) { int nx t.x dx[i]; int ny t.y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] -1) continue; int new_dis dis[t.x][t.y] 100; if (new_dis dis[nx][ny]) { dis[nx][ny] new_dis; q.push({ nx,ny,new_dis }); } } //斜方向 for (int i 0;i 4;i) { int nx t.x dx2[i]; int ny t.y dy2[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] -1) continue; int new_dis dis[t.x][t.y] 141; if (new_dis dis[nx][ny]) { dis[nx][ny] new_dis; q.push({ nx,ny,new_dis }); } } } if (ret 0x3f3f3f3f) cout -1 \n; else cout ret \n; } return 0; }问题 E: 小岛面积 - 期末考试试题题目描述111111 110001 100010 110111 010100 111111$$\begin{matrix} 1 1 1 1 1 1 \\ 1 1 0 0 0 1 \\ 1 0 0 0 1 0 \\ 1 1 0 1 1 1 \\ 0 1 0 1 0 0 \\ 1 1 1 1 1 1 \end{matrix} $$1 1 1 1 0 1​110111​100001​100111​101101​110101​上面矩阵的中的 111 代表海岸线000 代表小岛。求小岛面积的最大值。输入第一行输入一个整数 NNN (1≤N≤100)(1 \le N \le 100)(1≤N≤100)表示输入方阵的维数。输入一个 NNN 维方阵。输出小岛面积输入输出样例样例输入 #1复制6 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1样例输出 #1复制8提示DFS 求最大面积求最大连通块面积。dfs即可。#includevector #includeiostream #includeunordered_map using namespace std; int dx[4] { 0,0,-1,1 }; int dy[4] { 1,-1,0,0 }; int cnt 0; int n 0; //cur:当前是第几个连通块 void dfs(int x, int y, int cur, vectorvectorbool vis, vectorvectorint g, vectorvectorint mark) { //cout x y cur \n; vis[x][y] true; mark[x][y] cur;//在 mark矩阵中记录它属于第 cur个连通块 for (int i 0;i n;i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny n) continue; if (g[nx][ny] 1)//跳过海岸线 continue; if (vis[nx][ny]) continue; dfs(nx, ny, cur, vis, g, mark); } } int main() { cin n; vectorvectorintg(n, vectorint(n)); vectorvectorboolvis(n, vectorbool(n, false)); vectorvectorintmark(n, vectorint(n)); for (int i 0;i n;i) { for (int j 0;j n;j) cin g[i][j]; } int cur 1; for (int i 0;i n;i) { for (int j 0;j n;j) { if (!vis[i][j] g[i][j] ! 1) { dfs(i, j, cur, vis, g, mark); cur; } } } unordered_mapint, intmp; //mark矩阵里填满了数字0代表海水1、2、3...代表不同小岛 //遍历 mark用 mp统计每个数字连通块编号出现了多少次 for (auto arr : mark) { for (int e : arr) mp[e]; } int ret 0;//最大面积 for (auto e : mp) { //跳过编号为0的区域那是海水或未染色区域 if (e.first 0) continue; ret max(ret, e.second); } cout ret; return 0; }问题 F: 搜索进阶题目之A Knights Journey题目描述这位骑士已经厌倦了反复看到相同的黑白方块于是决定环游世界。每当骑士移动时它会向一个方向移动两个格子同时还会朝相反方向移动一个格子。骑士的世界就相当于棋盘上的格子。我们的骑士所居住的棋盘面积比普通的 8×88 \times 88×8 棋盘小但它仍然是矩形形状。你能帮助这位勇敢的骑士制定旅行计划吗输入输入开始以一个正整数 nnn 作为第一行。接下来的行包含了 nnn 个测试案例。每个测试案例由一行组成其中包含两个正整数 ppp 和 qqq 以及 1≤pq≤261 \le pq \le 261≤pq≤26 。这代表一个 p×qp \times qp×q 的棋盘其中 ppp 表示存在多少个不同的平方数 qqq 表示存在多少个不同的平方字母。这些就是拉丁字母表中的前 qqq 个字母。输出每个场景的输出都以一行文本开始该行包含Scenario #i:其中 iii 表示场景的编号从 111 开始计数。接着打印一行文本内容为以字典顺序排序的、能够遍历棋盘上所有棋子的路径。这条路径应以单行文本的形式给出通过连接已访问的棋子的名称来构建。每个棋子的名称由一个大写字母后跟一个数字组成。如果不存在这样的路径你应该输出“不可能”一词仅这一行内容即可。输入输出样例样例输入 #1复制3 1 1 2 3 4 3样例输出 #1复制Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4提示背景是国际象棋骑士也被称作马问题 I: 最小重量机器设计问题题目描述设某一机器由 nnn 个部件组成每一种部件都可以从 mmm 个不同的供应商处购得。设 wijw_{ij}wij​ 是从供应商 jjj 处购得的部件i的重量cijc_{ij}cij​ 是相应的价格。试设计一个回溯算法给出总价格不超过 ddd 的最小重量机器设计。对于给定的机器部件重量和机器部件价格计算总价格不超过 ddd 的最小重量机器设计。输入输入数据的第一行有 333 个正整数 n,mn, mn,m 和 ddd (n,m≤20,d≤200)n, m \le 20, d \le 200)n,m≤20,d≤200)。接下来的 2n2n2n 行每行 mmm 个数。前 nnn 行是 ccc后 nnn 行是 www。输出输出数据有两行第一行为计算出的最小重量第二行是每个部件的供应商每个供应商之间用空格分隔。输入输出样例样例输入 #1复制3 3 4 1 2 3 3 2 1 2 2 2 1 2 3 3 2 1 2 2 2样例输出 #1复制4 1 3 1问题 J: 0-1 背包问题题目描述试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数并将此函数用于解 0-1 背包问题。0-1 背包问题描述如下给定 nnn 种物品和一个背包。物品 iii 的重量是 wiw_iwi​其价值为 viv_ivi​背包的容量为 CCC。应如何选择装入背包的物品使得装入背包中物品的总价值最大?在选择装入背包的物品时对每种物品 iii 只有 2 种选择即装入背包或不装入背包。不能将物品 iii 装入背包多次也不能只装入部分的物品 iii。输入第一行有 2 个正整数 nnn 和 CCCnnn 是物品数CCC 是背包的容量。接下来的 1 行中有 nnn 个正整数表示物品的价值。第 3 行中有 nnn 个正整数表示物品的重量。输出将计算出的装入背包物品的最大价值和最优装入方案输出。第一行输出为Optimal value is输入输出样例样例输入 #1复制5 10 6 3 5 4 6 2 2 6 5 4样例输出 #1复制Optimal value is 15 1 1 0 0 1写了半天枚举最后超时了。超时之前一直给我报答案错误我就想报个超时让我死心也好啊。现在悬着的心终于死了。当然我也知道这样枚举包超时的但我就想试试万一数据范围小呢万一n30呢结果显而易见没有那么多万一。所以有空再改吧。#include iostream #include vector #include algorithm #define int long long using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, V; cin n V; vectorint w(n), v(n); for (int i 0; i n; i) cin w[i]; for (int i 0; i n; i) cin v[i]; int maxn -1; vectorvectorint ans; for (int i 0; i (1LL n); i) { vectorint tmp; int st i, cnt 0; int rest_v V, sum 0; bool flag true; while (st) { if (st 1) { tmp.push_back(cnt); rest_v - v[cnt]; sum w[cnt]; if (rest_v 0) { flag false; break; } } cnt; st 1; } if (flag rest_v 0 sum maxn) { maxn sum; ans.clear(); // ✅ 关键丢弃之前所有最优解 ans.push_back(tmp); // ✅ 只保留第一个最大 } } vectorint opt(n, 0); for (int e : ans[0]) opt[e] 1; cout Optimal value is\n; cout maxn \n; for (int i 0; i n; i) cout opt[i] \n[i n - 1]; return 0; }dfs也试了也不行。#includeiostream #includevector #includealgorithm #define int long long using namespace std; int n, V; vectorintw; vectorintv; int maxn; vectorintopt; vectorintx; vectorintbest; bool found; void dfs(int i, int rest_v, int sum, vectorinttmp) { if (found) return; if (i n) { if (sum maxn) { maxn sum; best.assign(tmp.begin(), tmp.end()); found true; } return; } if (rest_v 0) return; x[i] 0; dfs(i 1, rest_v, sum, tmp); if (rest_v - v[i] 0) { x[i] 1; tmp.push_back(i); dfs(i 1, rest_v - v[i], sum w[i], tmp); tmp.pop_back(); } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n V; w.resize(n); v.resize(n); for (int i 0;i n;i) cin w[i]; for (int i 0;i n;i) cin v[i]; maxn -1; found false; opt.assign(n, 0); x.assign(n, 0); vectorinttmp; dfs(0, V, 0, tmp); if (!best.empty()) for (int e : best) opt[e] 1; cout Optimal value is\n; cout maxn \n; for (int i 0;i n;i) cout opt[i] \n[in-1]; return 0; }