问题解决策略搜索训练3

P1588 [USACO07OPEN] Catch That Cow S题目描述FJ 丢了一头牛决定将其找回。FJ 和牛位于数轴上初始位置分别为 x 和 y牛保持不动。每次移动时若 FJ 处于位置 p他可移动至 p1、p−1 或 2×p。计算 FJ 抓住牛所需的最少移动次数。输入格式第一行为一个整数 t (1≤t≤10)表示数据组数接下来每行包含一个两个正整数 x,y (0x,y≤105)分别表示 FJ 和牛的坐标。输出格式对于每组数据输出最少步数每组数据间用换行隔开。输入输出样例输入 #1复制1 5 17输出 #1复制4这题用bfs。#includeiostream #includevector #includequeue #define int long long using namespace std; int n, k; int ans 0x3f3f3f3f; const int N 1e7; vectorintdis(N, 0x3f3f3f3f); signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin n k; dis[n] 0; queueintq; q.push(n); while (!q.empty()) { int t q.front(); q.pop(); if (dis[t] ans) continue; if (t k) { ans dis[t]; break; } if (t - 1 0 dis[t - 1] dis[t] 1) { q.push(t - 1); dis[t - 1] dis[t] 1; } if (t 1 N dis[t 1] dis[t] 1) { q.push(t 1); dis[t 1] dis[t] 1; } if (t * 2 N dis[t * 2] dis[t] 1) { q.push(t * 2); dis[t * 2] dis[t] 1; } } cout ans; return 0; }问题 B: 拯救行动题目描述公主被恶人抓走并关押在牢房的某个地方。牢房用 N×MN \times MN×M (N,M≤200)(N, M \le 200)(N,M≤200) 的矩阵表示。矩阵中的每项可以代表道路、墙壁#和守卫x。英勇的骑士决定孤身一人去拯救公主a。假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫骑士一旦遇到守卫必须杀死守卫才能继续前进。先假设骑士可以向上、下、左、右四个方向移动每移动一个位置需要 111 个单位时间杀死一个守卫需要额外的 111 个单位时间。同时假设骑士足够强壮有能力杀死所有的守卫。给定牢房矩阵公主、骑士和守卫在矩阵中的位置计算拯救行动成功需要花费的最短时间。输入第一行为一个整数 SSS表示输入的数据的组数有多组输入。随后有 SSS 组数据每组数据按如下格式输入两个整数代表 NNN 和 MMM (N,M≤200)(N, M \le 200)(N,M≤200)随后 NNN 行每行有 MMM 个字符。代表道路a代表公主r代表骑士x代表守卫#代表墙壁。输出如果拯救行动成功输出一个整数表示行动的最短时间如果不可能成功输出Impossible。输入输出样例样例输入 #1复制1 7 8 ###### #a#r ##x ### ### # 样例输出 #1复制13这题是图论——最短路Dijkstra算法-CSDN博客要用优先队列。从骑士(r)出发救公主(a)遇到守卫(x)需要额外时间墙壁(#)不能通过。#includeiostream #includevector #includequeue #includealgorithm #define int long long using namespace std; int n, m; int ex, ey, sx, sy; int ans 0; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; struct node { int x; int y; int val; //重载 运算符让优先队列成为小根堆值小的优先 bool operator(const node other) const { return val other.val; } }; signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int t; cin t; while (t--) { ans 0x3f3f3f3f; cin n m; vectorvectorintg(n, vectorint(m)); vectorvectorintdis(n, vectorint(m,0x3f3f3f3f)); for (int i 0;i n;i) { for (int j 0;j m;j) { char ch; cin ch; if (ch r)//起点 { sx i; sy j; } if (ch a)//终点 { ex i; ey j; } if (ch #)//墙壁 g[i][j] -1; if (ch x)//守卫 g[i][j] 1; } } dis[sx][sy] 0;//起点距离为0 priority_queuenode, vectornode, greaternode q; q.push({ sx,sy,0 });//起点入队 while (!q.empty()) { //取出当前距离最小的点 auto t q.top(); q.pop(); //当前距离大于已知最短距离 if (t.val dis[t.x][t.y]) continue; //找到终点记录答案并退出 if (t.x ex t.y ey) { ans dis[t.x][t.y]; break; } for (int i 0;i 4;i) { int cx t.x dx[i]; int cy t.y dy[i]; //检查新位置是否合法且不是墙壁 if (cx 0 cx n cy 0 cy m g[cx][cy] ! -1) { //计算新距离 int d dis[t.x][t.y] 1 g[cx][cy]; if (dis[cx][cy] d)//如果找到更短路径 { dis[cx][cy] d;//更新距离 q.push({ cx,cy,d });//新节点入队 } } } } if (ans 0x3f3f3f3f) cout Impossible\n; else cout ans \n; } return 0; }问题 C: 鸣人和佐助题目描述已知一张地图以二维矩阵的形式表示以及佐助和鸣人的位置。地图上的每个位置都可以走到只不过有些位置上有大蛇丸的手下需要先打败大蛇丸的手下才能到达这些位置。鸣人有一定数量的查克拉每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上、下、左、右四个方向移动每移动一个距离需要花费 111 个单位时间打败大蛇丸的手下不需要时间。如果鸣人的查克拉消耗完了则只可以走到没有大蛇丸手下的位置不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动大蛇丸的手下也不移动。请问鸣人追上佐助最少需要花费多少时间输入输入的第一行包含三个整数 M,N,TM, N, TM,N,T代表 MMM 行 NNN 列的地图和鸣人初始的查克拉数量其中0M,N2000 \lt M, N \lt 2000M,N2000≤T100 \le T \lt 100≤T10。后面是 MMM 行 NNN 列的地图其中代表鸣人代表佐助*代表通路#代表大蛇丸的手下。输出输出包含一个整数 RRR代表鸣人追上佐助最少花费的时间。如果鸣人无法追上佐助则输出-1。输入输出样例样例输入 #1复制4 4 1 # # # * * # # # # # * * * *样例输出 #1复制6提示此题数据并不完善实际上使用dfs是会超时的#includeiostream #includevector #includequeue #includealgorithm #define int long long using namespace std; int n, m, t; int ex, ey, sx, sy; int ans 0; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; struct node { int x; int y; int val; int c; }; signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); ans 0x3f3f3f3f; cin n m t; vectorvectorintg(n, vectorint(m)); //记录每个位置在不同查克拉下的最短时间 vectorvectorvectorintdis(n, vectorvectorint(m, vectorint(t 1, 0x3f3f3f3f))); for (int i 0;i n;i) { for (int j 0;j m;j) { char ch; cin ch; if (ch )//起点 { sx i; sy j; } if (ch )//终点 { ex i; ey j; } if (ch *)//通路 g[i][j] 0; if (ch #)//大蛇丸的手下 g[i][j] 1; } } dis[sx][sy][t] 0;//起点距离为0 queuestruct nodeq; q.push({ sx,sy,0,t });//起点入队 while (!q.empty()) { //取出当前距离最小的点 auto t q.front(); q.pop(); //当前距离大于已知最短距离 if (t.val dis[t.x][t.y][t.c]) continue; //找到终点记录答案并退出 if (t.x ex t.y ey) { ans dis[t.x][t.y][t.c]; break; } for (int i 0;i 4;i) { int cx t.x dx[i]; int cy t.y dy[i]; //检查新位置是否合法 if (cx 0 cx n cy 0 cy m) { //计算新距离 int d dis[t.x][t.y][t.c] 1 ; int ct t.c; if (g[cx][cy] 1) ct t.c - 1; if (ct 0) continue; if (dis[cx][cy][ct] d)//如果找到更短路径 { dis[cx][cy][ct] d;//更新距离 q.push({ cx,cy,d,ct });//新节点入队 } } } } if (ans 0x3f3f3f3f) cout -1\n; else cout ans \n; return 0; }问题 D: 迷宫问题题目描述定义一个二维数组int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0 };它表示一个迷宫其中的 111 表示墙壁000 表示可以走的路只能横着走或竖着走不能斜着走要求编程序找出从左上角到右下角的最短路线。输入一个 5×55 \times 55×5 的二维数组表示一个迷宫。数据保证有唯一解。输出左上角到右下角的最短路径格式如样例所示。输入输出样例样例输入 #1复制0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0样例输出 #1复制(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)#includeiostream #includevector #includequeue #includealgorithm #define int long long using namespace std; int n 5; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; struct node { int x; int y; }; vectorstruct nodeans; vectorvectorboolvis(5, vectorbool(5, false)); vectorvectorintg(5, vectorint(5)); vectorvectorintdis(5, vectorint(5,0x3f3f3f3f)); void dfs(int x, int y) { //cout x x y y \n; if (x 4 y 4) { for (auto e : ans) { cout ( e.x , e.y )\n; } return; } for (int i 0;i 4;i) { int cx x dx[i]; int cy y dy[i]; if (cx 0 cx 5 cy 0 cy 5 g[cx][cy] ! 1 !vis[cx][cy] dis[x][y] 1 dis[cx][cy]) { vis[cx][cy] true; ans.push_back({ cx,cy }); dis[cx][cy] dis[x][y] 1; dfs(cx, cy); vis[cx][cy] false; ans.pop_back(); } } } signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); for (int i 0;i n;i) { for (int j 0;j n;j) cin g[i][j]; } ans.push_back({ 0,0 }); dis[0][0] 0; vis[0][0] true; dfs(0, 0); return 0; }问题 E: 变换的迷宫题目描述你身处一个 R×CR \times CR×C 的迷宫中当前位置用S表示迷宫的出口用E表示。迷宫中有一些石头用#表示还有一些可以随意走动的区域用.表示。初始时间为 000 时你站在地图中标记为S的位置上。你每移动一步向上、下、左、右方向移动会花费一个单位时间。你必须一直保持移动不能停留在原地不走。当前时间是 KKK 的倍数时迷宫中的石头就会消失此时你可以走到这些位置上。再其余的时间中你不能走到石头所在的位置。求你从初始位置走到迷宫出口最少需要花费多少个单位时间。如果无法走到出口则输出Oop!。其中0R,C≤1000 \lt R, C \le 1000R,C≤1002≤K≤102 \le K \le 102≤K≤10。输入第一行是一个正整数 TTT表示有 TTT 组数据。每组数据的第一行包含三个用空格分开的正整数分别是 R,C,KR, C, KR,C,K。接下来的 RRR 行中每行包含 CCC 个字符分别可能是S、E、#或.。其中0T≤200 \lt T \le 200T≤200R,C≤1000 \lt R, C \le 1000R,C≤1002≤K≤102 \le K \le 102≤K≤10。输出对于每组数据如果能够走到迷宫的出口则输出一个正整数表示最少需要花费的单位时间否则输出Oop!。输入输出样例样例输入 #1复制1 6 6 2 ...S.. ...#.. .#.... ...#.. ...#.. ..#E#.样例输出 #1复制7#includeiostream #includevector #includequeue #includealgorithm #define int long long using namespace std; int n, m, k; int ex, ey, sx, sy; int ans 0; int dx[4] { 0,0,1,-1 }; int dy[4] { 1,-1,0,0 }; struct node { int x; int y; int val; int cnt; //重载 运算符让优先队列成为小根堆值小的优先 bool operator(const node other) const { return val other.val; } }; signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int t; cin t; while (t--) { ans 0x3f3f3f3f; cin n m k; vectorvectorintg(n, vectorint(m)); vectorvectorvectorintdis(n, vectorvectorint(m, vectorint(k 1, 0x3f3f3f3f))); 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 E)//终点 { ex i; ey j; } if (ch #)//墙壁 g[i][j] 1; } } dis[sx][sy][0] 0;//起点距离为0 priority_queuenode, vectornode, greaternode q; q.push({ sx,sy,0,0 });//起点入队 while (!q.empty()) { //取出当前距离最小的点 auto t q.top(); q.pop(); //当前距离大于已知最短距离 if (t.val dis[t.x][t.y][t.cnt]) continue; //找到终点记录答案并退出 if (t.x ex t.y ey) { ans dis[t.x][t.y][t.cnt]; break; } for (int i 0;i 4;i) { int cx t.x dx[i]; int cy t.y dy[i]; //检查新位置是否合法 if (cx 0 cx n cy 0 cy m) { //计算新距离 int d dis[t.x][t.y][t.cnt] 1; int c t.cnt; if (g[cx][cy] 1 (c 1) % k ! 0) { c (c 1) % k; d; } if (dis[cx][cy][c] d)//如果找到更短路径 { dis[cx][cy][c] d;//更新距离 q.push({ cx,cy,d,c });//新节点入队 } } } } if (ans 0x3f3f3f3f) cout Oop\n; else cout ans \n; } return 0; }