目录

• 棋盘问题 （POJ-1321）
• Dungeon Master （POJ-2251）
• Catch That Cow (POJ-3278)
• Fliptile （POJ-3279）
• Find The Multiple （POJ-1426）
• Prime Path （POJ-3126）
• Shuffle'm Up （POJ-3087）
• Pots(POJ-3414)
• Fire Game（FZU-2150）
• Fire！(UVA-11624)
• 迷宫问题（POJ-3984）
• Oil Deposits（HDU-1241）
• 非常可乐（HDU-1495）
• Find a way（HDU-2612）

poj不支持万能头文件
kuangbin专题链接传送门

棋盘问题 （POJ-1321）

题目链接：传送门
kuangbin专题链接传送门
题意：给定一个n*n的不规则棋盘，要求放入k个棋子，其中“#”能放棋子，“.”空白不能放棋子，且对于已经放了的棋子不能再放入同一行、同一列，求出有多少种放棋子的方案

其实不难，就是一个深度遍历加上回溯

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; int ans; //计数答案 int n, k; //n*n大小 放k个棋子 char mp[20][20]; //地图 bool vis[20]; //检查每一列是否遍历过 int DFS(int x,int y) //深度遍历 x表示访问的行数，y是表示已经填了的棋子数量 {if (y >= k) //如果k个棋子全部放完，ans++并返回{ans++;return 0;}for (int i = x; i < n; i++) //行遍历{for (int j = 0; j < n; j++) //每一列都遍历一次{if(!vis[j]&&mp[i][j]=='#') //那一列未被访问且可填入{vis[j] = true; //标记该已列被访问DFS(i + 1, y + 1); //访问下一个点，下一个点是从下一行开始vis[j] = false; //回溯 标记该列未被访问}}} } int main() {while (cin >> n >> k) //多次输入{if (n == -1 && k == -1) //结束输入break;memset(vis, false, sizeof(vis)); //初始化for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cin >> mp[i][j]; //输入}}ans = 0; //ans初始化DFS(0, 0); //从0行开始遍历cout << ans << endl; //输出结果}return 0; }

Dungeon Master （POJ-2251）

题目链接：传送门
kuangbin专题链接传送门

题意：有一个由L层，每一层有R行和C列的地牢，S表示起点，E表示终点，每走一步时间加一，你只能上下左右移动，问你是否能逃脱出地牢。如果能，输出逃脱地牢的时间，不能则被困住

思路：三维广度搜索，套用一维或者二维BFS模板就能写出来

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif #define ll long long using namespace std; struct node {int x, y, z; }; //a,b,c分别表示在L,R,C上的方向 int a[6]={1,-1,0,0,0,0}; int b[6]={0,0,1,-1,0,0}; int c[6]={0,0,0,0,1,-1}; int L, R, C; bool check(int x,int y,int z) //判断函数，检查值是否越界 {return (x >= 0 && x < R && y >= 0 && y < C && z >= 0 && z < L); } const int maxn = 35; const int INF = 0x3f3f3f3f; //无穷大 int d[maxn][maxn][maxn]; // 记录从起点到每个点的距离 char mp[maxn][maxn][maxn]; //地牢 int sx, sy, sz; //起点 x表示行，y表示列，z表示层数 int ex, ey, ez; //终点 int ans; //答案 /******广度遍历******/ int bfs() {memset(d, INF, sizeof(d)); //距离初始化queue<node>q;node now;now.x=sx;now.y=sy;now.z=sz; d[now.z][now.x][now.y]=0; //起点距离为0q.push(now);while(!q.empty()){now = q.front();q.pop();if (now.x == ex && now.y == ey && now.z == ez) //终点停止遍历，跳出循环break;node next;for (int i = 0; i < 6; i++){next.x = now.x + a[i];next.y = now.y + b[i];next.z = now.z + c[i];if (check(next.x, next.y, next.z) && d[next.z][next.x][next.y] == INF && mp[next.z][next.x][next.y] != '#') //判断是否符合条件{d[next.z][next.x][next.y] = d[now.z][now.x][now.y] + 1; //距离加一q.push(next); //入队}}}return d[ez][ex][ey]; //返回终点值 } int main() {while (cin >> L >> R >> C){if (L + R + C == 0) //终止输入条件break;for (int i = 0; i < L; i++){for (int j = 0; j < R; j++){for (int k = 0; k < C; k++){cin >> mp[i][j][k]; // 输入if (mp[i][j][k] == 'S') // 找起点{sx = j;sy = k;sz = i;}if (mp[i][j][k] == 'E') // 找终点{ex = j;ey = k;ez = i;}}}getchar(); //每一层输入时有空行，回车 用getchar抵消}ans = bfs();if (ans == INF || ans == 0) //判断cout << "Trapped!" << endl;elsecout << "Escaped in " << ans << " minute(s)." << endl;}return 0; }

Catch That Cow (POJ-3278)

题目链接：传送门
kuangbin专题链接传送门
题意：农夫抓牛，农夫在n点，牛在k点，步行只能前后走一步，传送则直接到2*x（x为农夫当前位置），每传送或者步行一次花费一秒，求农夫最少需要多少秒才能抓住牛

简单一维BFS，模板题

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; int n, k; //农夫和牛的位置 const int maxn = 1e5 + 5; bool vis[maxn]; struct node {int x, step; //位置，步数 }; bool check(int x) {return (x >= 0 && x <= maxn); //判断是否越界 } queue<node> q; int bfs() {node start;start.x = n;start.step = 0;vis[start.x] = true;q.push(start);while (!q.empty()){start = q.front();q.pop();if(k==start.x)break;node next;for (int i = 0; i < 3; i++){if (i == 0) next.x = start.x - 1; //向后走if (i == 1)next.x = start.x + 1; //向前走if (i == 2)next.x = start.x * 2; //传送if (check(next.x) && !vis[next.x]){next.step = start.step + 1; vis[next.x] = true;q.push(next);}}}return start.step; } int main() {memset(vis, false, sizeof(vis)); // 初始化while (!q.empty())q.pop(); //清空队列cin >> n >> k;if (n >= k) //n比k大不能使用传送，只能一步步走，直接用减法计算cout << n - k << endl;elsecout << bfs() << endl; return 0; }

Fliptile （POJ-3279）

题目链接：传送门
kuangbin专题链接传送门
题意：给定一个m*n的图，里面有黑白两钟颜色的瓷砖，黑色瓷砖的背面是白色，白色瓷砖的背面是黑色，小牛需要将所以的瓷砖翻转成白色，每翻转一个瓷砖，它的上下左右的瓷砖也会跟着翻转，求小牛翻转的最小次数。有多个解时，输出字典序最小的一组。

利用局部推全局，确定第一行后再确定后一行，依次判断，直到判断最后一行。
判断最后一行是否全为白色来确定当前方案是否可行。
时间复杂度为 O(n * m * 2^m)。

#include<iostream> #include<cstring> using namespace std; const int maxn = 17; const int INF = 0x3f3f3f3f; int dir[5][2] = {{0, 0},{1, 0},{0, -1},{-1, 0},{0, 1}, }; int mp[maxn][maxn], temp[maxn][maxn], ans[maxn][maxn], res, cnt, m, n; int getcolor(int x,int y) {int t = mp[x][y];for (int i = 0; i < 5;i++){int xi = x + dir[i][0];int yi = y + dir[i][1];if (xi >= 0 && xi < m && yi >= 0 && yi < n)t += temp[xi][yi];}return t % 2; }void DFS() {for (int i = 1; i < m; i++){for (int j = 0; j < n; j++){if(getcolor(i-1,j)){temp[i][j] = 1;cnt++;}if(cnt>res)return;}}for (int i = 0; i < n; i++)if(getcolor(m-1,i))return;if(cnt<res)memcpy(ans, temp,sizeof(temp)), res = cnt; } int main() {while(cin>>m>>n){res = INF;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)cin >> mp[i][j];for (int i = 0; i < 1 << n; i++){cnt = 0;memset(temp, 0, sizeof(temp));for (int j = 0; j < n; j++){temp[0][n - 1 - j] = i >> j & 1;if(temp[0][n-1-j])cnt++;}DFS();}if(res==INF)cout << "IMPOSSIBLE" << endl;else{for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if(j>0)cout << " ";cout << ans[i][j];}cout << endl;}}}return 0; }

Find The Multiple （POJ-1426）

题目链接：传送门
kuangbin专题链接传送门
题目大意：给定一个数n，找出一个只包含0和1的非零十进制数m，使得m和n成倍数关系

数据太水了

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; #define ll long long ll n; void bfs() {queue<ll> q;q.push(1);while (!q.empty()){ll t = q.front();q.pop();ll x = t * 10; //0ll y = x + 1; //1if (t % n == 0) //倍数关系{cout << t << endl;return;}q.push(x), q.push(y);} } int main() {while (cin >> n) {if (n == 0)break;bfs();}return 0; }

Prime Path （POJ-3126）

链接：传送门
kuangbin专题链接传送门
题目大意：从一个素数m变成另一个素数n最少需要几步，每一步只能变一个位上的数，而且中间变换的数也是素数

素数筛子法，先打表，将素数存入一个数组中，再分离个十百千，位数分别处理

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; const int maxn = 1e5 + 10; int prime[maxn]={0,0}; bool vis[maxn]; int flag[12]; int a, b; typedef long long ll; /*****素数筛子******/ void getprime() {for (int i = 2; i <= 9999;i++) //假设所以数都为素数prime[i] = 1;for (int i = 2; i <= 9999;i++){if(prime[i]){for (int j = i * 2; j <= 9999;j+=i){prime[j] = 0; //素数的倍数都是非素数}}} } typedef struct node {int x;ll step;friend bool operator <(node a,node b){return a.step > b.step; } }Node;int check(int x) {if (x < 1000 || x > 9999 || vis[x])return 1;return 0; }int bfs() {priority_queue<Node> q;while (!q.empty())q.pop(); memset(vis, false, sizeof(vis));Node now, next;now.x = a;now.step = 0;vis[a] = true;q.push(now);while (!q.empty()){now = q.top();q.pop();if (now.x == b)return now.step;/*****分离******/int ge = now.x % 10; //个位int shi = now.x / 10 % 10; //十位int bai = now.x / 100 % 10; //百位int qian = now.x / 1000; //千位/*******个位*******/memset(flag, false, sizeof(flag));flag[ge] = 1;for (int j = 1; j <= 9; j += 2){if(!flag[j]){int temp = j + shi * 10 + bai * 100 + qian * 1000; //注意j是个位if(!check(temp)&&prime[temp]){next.x = temp;next.step = now.step + 1;q.push(next);}vis[temp] = true;}}/**********十位******/memset(flag,false,sizeof(flag));flag[shi] = 1;for (int j = 0; j <= 9; j++){if(!flag[j]){int temp = ge + j * 10 + bai * 100 + qian * 1000; //j是十位if(!check(temp)&&prime[temp]){next.x = temp;next.step = now.step + 1;q.push(next);}vis[temp] = true;}}/***********百位********/memset(flag,false,sizeof(flag));flag[bai] = 1;for (int j = 0; j <= 9; j++){if(!flag[j]){int temp = ge + shi * 10 + j * 100 + qian * 1000; //j是百位if(!check(temp)&&prime[temp]){next.x = temp;next.step = now.step + 1;q.push(next);}vis[temp] = true;}}/*********千位********/memset(flag,false,sizeof(flag));flag[qian] = 1;for (int j = 1; j <= 9; j++){if(!flag[j]){int temp = ge + shi * 10 + bai * 100 + j * 1000; //j是千位if(!check(temp)&&prime[temp]){next.x = temp;next.step = now.step + 1;q.push(next);}vis[temp] = true;}}}return -1; } int main() {getprime();int n, ans;cin >> n;for (int i = 1; i <= n; i++){cin >> a >> b;ans = bfs();if(ans==-1)cout << "Impossible" << endl;elsecout << ans << endl;}return 0; }

Shuffle’m Up （POJ-3087）

题目链接：传送门
kuangbin专题链接传送门

题目大意：给定字符串s1,s2和s3，s2的第一个字符先放入s12，然后放入s1的第一个字符，类似于s2,s1,s2,s1,s2,s1…放完后的s12长度前一半是s1新状态，后一半是s2新状态， 重复以上操作，看得到s12和给定的s3是否相同的，相同则输出经历的步骤数，不相同则输出-1

主要还是得会字符串操作

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; string s1, s2, s12; int n; int dfs(string a,string b,int step) {if (a + b == s12) //得到目标字符串return step;string temp = "";for (int i = 0; i < n; i++)temp = temp + b[i] + a[i];a = temp.substr(0, n); //substr是复制temp中的第0个位置开始的长n的字符串b = temp.substr(n, n);if (a.compare(s1) == 0 && b.compare(s2) == 0) //如果变换后的字符串与初始串相同，则变换失败return -1;elsereturn dfs(a, b, step + 1); } int main() {int t;cin >> t;for (int i = 1; i <= t; i++){cin >> n >> s1 >> s2 >> s12;cout << i << " " << dfs(s1, s2, 0) << endl;}return 0; }

Pots(POJ-3414)

题目链接：传送门
kuangbin专题链接传送门

题目大意，给甲乙两个空桶，容量分别为A，B，再给定一个目标容量C，以及三种操作（把某个桶的水加满；把某个桶的水全倒掉；把某个桶的水倒入另一个桶）
问是否能使任意一个桶的水量达到给定容量C，如果能，输出最短步骤的数量以及具体操作，如果不能输出“impossible”。

题意：两个桶，六种操作， 每种操作具体分类就行，不难。

#include <iostream> #include <cstdio> #include <queue> using namespace std;const int maxn = 500;int a, b, c; bool vis[maxn][maxn]; bool flag = false; string str[10] = {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)","POUR(2,1)"};struct node {int x, y, step; string s;// node (int x, int y, int step, string s):x(x), y(y), step(step),s(s){} };void bfs () {queue<node>q;vis[0][0] = true;q.push({0, 0, 0, "0"});while(!q.empty()){node tmp = q.front();q.pop();if (tmp.x == c || tmp.y == c){flag = 1;cout << tmp.step << endl;for (int i = 1; i < tmp.s.length(); ++ i)cout << str[tmp.s[i]-'0'] << endl;return;}if (tmp.x < a) //甲桶的水比桶容量小{if (!vis[a][tmp.y]){vis[a][tmp.y] = true;q.push({a, tmp.y, tmp.step + 1, tmp.s + "1"});}}if (tmp.y < b) //乙桶的水比桶容量小{if (!vis[tmp.x][b]){vis[tmp.x][b] = true;q.push({tmp.x, b, tmp.step + 1, tmp.s + "2"});}}if (tmp.x != 0) //甲桶里有水{if (!vis[0][tmp.y]){vis[0][tmp.y] = true;q.push({0, tmp.y, tmp.step + 1, tmp.s + "3"});}}if (tmp.y != 0) //乙桶里有水{if (!vis[tmp.x][0]){vis[tmp.x][0] = true;q.push({tmp.x, 0, tmp.step + 1, tmp.s + "4"});}}if (tmp.x != 0 && tmp.y < b) //甲桶里有水且乙桶的水比桶容量小{int nx, ny;if (tmp.x <= b - tmp.y) {nx = 0;ny = tmp.x + tmp.y;}else{nx = tmp.x + tmp.y - b;ny = b;}if (!vis[nx][ny]){vis[nx][ny] = true;q.push({nx, ny, tmp.step + 1, tmp.s + "5"});}}if (tmp.y != 0 && tmp.x < a) //乙桶里有水且甲桶的水比桶容量小{int nx, ny;if (tmp.y <= a-tmp.x){nx = tmp.x + tmp.y;ny = 0;}else{nx = a;ny = tmp.x + tmp.y - a;}if (!vis[nx][ny]){vis[nx][ny] = true;q.push({nx, ny, tmp.step + 1, tmp.s + "6"});}}} }int main () {cin >> a >> b >> c;bfs ();if (!flag)cout << "impossible" << endl;return 0; }

Fire Game（FZU-2150）

题目链接失效，oj平台没了，该题暂未通过oj测评
传送门

题目大意：给定m行n列的地图，’#'表示草地，‘.’表示平地，现要选地图两点开始点火，问是否能烧完所有草地，如果能，输出烧完所有草地所需最少时间，如果不能，输出-1；

思路：双起点BFS，写法与传统的BFS类似，这里不多做赘述，直接看代码

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; int m, n; //n是行，m是列 int dir[4][2] = {{1, 0},{-1, 0},{0, 1},{0, -1} }; const int maxn = 15; const int INF = 0x3f3f3f3f; bool vis[maxn][maxn]; char mp[maxn][maxn]; int d[maxn][maxn]; bool check(int x, int y) {return (x >= 0 && x < n && y >= 0 && y < m); } struct node {int x;int y; }; vector<node> qq; int ans; int bfs(int sx1,int sy1,int sx2,int sy2) {queue<node> q;memset(d, 0, sizeof(d));memset(vis, false, sizeof(vis));node start1, start2;// start1.x = sx1;// start1.y = sy1;q.push({sx1,sy1});vis[sx1][sy1] = true;// start2.x = sx2;// start2.y = sy2;q.push({sx2,sy2});vis[sx2][sy2] = true;while(!q.empty()){node start = q.front();q.pop();node next;for (int i = 0; i < 4; i++){next.x = start.x + dir[i][0];next.y = start.y + dir[i][1];if (check(next.x, next.y) && !vis[next.x][next.y] && mp[next.x][next.y] == '#'){vis[next.x][next.y] = true;d[next.x][next.y] = d[start.x][start.y] + 1;q.push(next);}}}int t = -INF;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (!vis[i][j] && mp[i][j] == '#')return -1;if (t < d[i][j])t = d[i][j];}}return t; } int main() {int t;cin >> t;for (int T = 1; T <= t; T++){cin >> n >> m;qq.clear();for (int i = 0; i < n; i++){scanf("%s", mp[i]);for (int j = 0; j < m; j++){if(mp[i][j]=='#'){node a;a.x = i;a.y = j;qq.push_back(a);}}}ans = INF;for (int i = 0; i < qq.size(); i++){for (int j = i; j < qq.size(); j++){int temp = bfs(qq[i].x, qq[i].y, qq[j].x, qq[j].y);if (temp == -1){continue;}if (temp < ans)ans = temp;}}if (ans == INF)ans=-1;cout << "Case " << T << ": " << ans << endl;}return 0; }

Fire！(UVA-11624)

题目链接：传送门
kuangbin专题链接传送门

题目大意：给定R行C列的迷宫，其中“J”表示Joe,“F”表示火的位置，“.”表示空地，“#”表示墙壁，问Joe能否在火烧到他之前逃离迷宫，如果能，输出逃出迷宫所需要的最短时间，如果不能，则输出“IMPOSSIBLE”。
思路：先给火用BFS，记录火烧到各点所需要的时间，再给Joe BFS，判断Joe在到下一点时，火是否烧到。

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; const int maxn = 1010; const int INF = 0x3f3f3f3f; int t, r, c, step[maxn][maxn], sx, sy; //step记录火到x，y点的时间 bool vis[maxn][maxn]; //记录是否走过 char a[maxn][maxn]; struct node {int x, y, t; }; queue <node> q; int dir[4][2] = { //四个方向{1, 0},{-1, 0},{0, 1},{0, -1} }; bool check(int x,int y) //检查函数合理性 {return (x >= 1 && x <= r && y >= 1 && y <= c); } void FireBfs() //火 {while (!q.empty()) {node now = q.front();q.pop();for (int i = 0; i < 4; ++i) {int dx = now.x + dir[i][0];int dy = now.y + dir[i][1];if (check(dx,dy) && a[dx][dy] != '#' && step[dx][dy] == INF) {q.push(node{dx, dy, 0});step[dx][dy] = step[now.x][now.y] + 1; //记录时间}}} }void JoeBfs() //Joe {q.push(node{sx, sy, 0});vis[sx][sy] = true;while (!q.empty()) {node now = q.front();q.pop();if (now.x == r || now.x == 1 || now.y == 1 || now.y == c) {cout << now.t + 1 << endl;return;}for (int i = 0; i < 4; ++i) {int dx = now.x + dir[i][0];int dy = now.y + dir[i][1];if (check(dx,dy) && a[dx][dy] != '#' && !vis[dx][dy] && (now.t + 1 < step[dx][dy])) //在时间上Joe比火早到{q.push(node{dx, dy, now.t + 1});vis[dx][dy] = true;}}}cout << "IMPOSSIBLE" << endl; }int main() {cin >> t;while (t--) {while (!q.empty()) q.pop();memset(vis, false,sizeof(vis));memset(step, INF,sizeof(step));cin >> r >> c;for (int i = 1; i <= r; ++i) {for (int j = 1; j <= c; ++j) {cin >> a[i][j];if (a[i][j] == 'J') //找Joe的起始坐标{sx = i;sy = j;}if (a[i][j] == 'F') //找火的起始坐标{q.push(node{i, j, 0});step[i][j] = 0;}}}FireBfs();while (!q.empty()) q.pop();JoeBfs();}return 0; }

迷宫问题（POJ-3984）

题目链接：传送门
kuangbin专题链接传送门
题意：给定一个5行5列的迷宫，求从左上角走到右下角的路径。

思路：没有思路，数据水；
解法一：

#include<iostream> using namespace std; int main(){cout << "(0, 0)" << endl;cout << "(1, 0)" << endl;cout << "(2, 0)" << endl;cout << "(2, 1)" << endl;cout << "(2, 2)" << endl;cout << "(2, 3)" << endl;cout << "(2, 4)" << endl;cout << "(3, 4)" << endl;cout << "(4, 4)" << endl;//最水的数据了return 0; }

解法二：

#include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> #include <queue> #include <string> #include <map> using namespace std; struct node {int x,y,step; }s; node pre[10][10]; int maps[10][10]; int vis[10][10]; int dir[2][2]={1,0,0,1}; void dfs (int x, int y) {if (x==0 && y== 0){printf("(%d, %d)\n",x,y);return;}node t = pre[x][y];dfs(t.x,t.y); printf("(%d, %d)\n",x,y); } void bfs () {queue <node>q;q.push(s);vis[0][0] = 1;while (!q.empty()){node t,tt;t = q.front();q.pop();tt.step = t.step+1;for (int i = 0; i < 2; i++){tt.x = t.x+dir[i][0];tt.y = t.y+dir[i][1];pre[tt.x][tt.y] = t;if (tt.x == 4 && tt.y ==4)return;if (tt.x < 5 && tt.y <5 && !vis[tt.x][tt.y] && !maps[tt.x][tt.y]){vis[tt.x][tt.y] = 1;q.push(tt);}}} } int main() {memset(vis,0,sizeof (vis));for (int i =0; i < 5; i++)for (int j = 0; j < 5;j++)cin>>maps[i][j];s.x = 0;s.y = 0;s.step = 0;bfs();dfs(4,4);return 0; }

Oil Deposits（HDU-1241）

题目链接：传送门
kuangbin专题链接传送门

题目大意：
给定m行n列的地图，在地图上找出有多少种不团类型的油田，规定：油田用‘@’表示，平地用‘*’表示，规定：若在‘@’八个不同的方向（上，下，左，右，左上，右上，左下，右下）有‘@’，则这两个‘@’是同一类型的油田

思路：广度遍历，遇到未标记的‘@’就进队，走过的‘@’就做个标记，然后再四周寻找‘@’做相同的操作，直至队列为空。

代码：

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; int dir[8][2] = { //八个不同的方向{1, 0},{-1, 0},{0, 1},{0, -1},{1, -1},{1, 1},{-1, 1},{-1, -1} }; const int maxn = 105; int t, n, m; char a[maxn][maxn]; struct node {int x, y; }; bool vis[maxn][maxn]; //标记 bool check(int a,int b){ //判断点是否合法return (a >= 0 && a < m && b >= 0 && b < n); } int BFS() {t = 0;queue<node> q;memset(vis, false, sizeof(vis)); //初始化while (!q.empty()) q.pop();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (a[i][j] == '@' && !vis[i][j]){vis[i][j] = true;node temp;temp.x = i;temp.y = j;q.push(temp);t++;while (!q.empty()){node now = q.front();q.pop();node next;for (int i = 0; i < 8; i++){next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];if (check(next.x, next.y) && !vis[next.x][next.y] && a[next.x][next.y] == '@'){vis[next.x][next.y] = true;q.push(next);}}} }return t; } int main(){while (cin >> m >> n){if (m == 0 || n == 0)break;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)cin >> a[i][j];cout << BFS() << endl;}return 0; }

非常可乐（HDU-1495）

题目链接：传送门
kuangbin专题链接传送门
题目大意：给定一瓶Ｓ升的可乐，将可乐分别倒入容量为Ａ，Ｂ的两个杯子中，它们三个之间可以互相倒可乐。问这个三个之间的任意两个容器能不能平分Ｓ升的可乐。

思路：如果Ｓ是奇数的话，一定不能平分的。如果S是偶数。共有六种倒法S-A,A-S,S-B,B-S,A-B,B-A。两种情况：１.一个容器里的可乐全倒进另一个容器　２．一个容器将另一个容器倒满并且还剩可乐。将三个容器出现过的情况用一个三维数组进行标记。

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; int s, m, n; struct node{int x, y, z, w; }; const int maxn = 110; bool flag,vis[maxn][maxn][maxn]; int ans; int BFS(){flag = false;queue<node> q;memset(vis, false, sizeof(vis));q.push({s, 0, 0, 0});int c = s / 2;vis[s][0][0] = true;while (!q.empty()){node temp = q.front();q.pop();int tx, ty, tz;/****判断****/if (temp.x == c && temp.y == c){flag = true;ans = temp.w;break;}else if (temp.x == c && temp.z == c){flag = true;ans = temp.w;break;}else if (temp.y == c && temp.z == c){flag = true;ans = temp.w;break;}/****S-A****/if (temp.x > (m - temp.y)){tx = temp.x - m + temp.y;ty = m;tz = temp.z;}else{tx = 0;ty = temp.x + temp.y;tz = temp.z;}if(!vis[tx][ty][tz]){vis[tx][ty][tz] = true;q.push({tx, ty, tz, temp.w + 1});}/****A-S****/tx = temp.x + temp.y;ty = 0;tz = temp.z;if(!vis[tx][ty][tz]){vis[tx][ty][tz] = true;q.push({tx, ty, tz, temp.w + 1});}/****S-B****/if (temp.x > (n - temp.z)){tx = temp.x - n + temp.z;ty = temp.y;tz = n;}else{tx = 0;ty = temp.y;tz = temp.x + temp.z;}if(!vis[tx][ty][tz]){vis[tx][ty][tz] = true;q.push({tx, ty, tz, temp.w + 1});}/****B-S****/tx = temp.x + temp.z;ty = temp.y;tz = 0;if(!vis[tx][ty][tz]){vis[tx][ty][tz] = true;q.push({tx, ty, tz, temp.w + 1});}/****A-B****/if (temp.y > (n - temp.z)){tx = temp.x;ty = temp.y - n + temp.z;tz = n;}else{tx = temp.x;ty = 0;tz = temp.z + temp.y;}if(!vis[tx][ty][tz]){vis[tx][ty][tz] = true;q.push({tx, ty, tz, temp.w + 1});}/****B-A****/if(temp.z>(m-temp.y)){tx = temp.x;ty = m;tz = temp.z - m + temp.y;}else{tx = temp.x;ty = temp.y+temp.z;tz = 0;}if(!vis[tx][ty][tz]){vis[tx][ty][tz] = true;q.push({tx, ty, tz, temp.w + 1});}} } int main(){while (cin >> s >> m >> n){if (s == 0 || m == 0 || n == 0)break;if (s % 2 == 1){cout << "NO" << endl;continue;}BFS();if (flag)cout << ans << endl;elsecout << "NO" << endl;}return 0; }

Find a way（HDU-2612）

题目链接：传送门
kuangbin专题链接传送门

题目大意：给定一个图，甲乙两人在最短的时间内找到KFC

思路：两个人分别BFS一遍，分别用两个数组存储到每个KFC的时间，最后在进行比较，选择最短时间。输出记得乘以11。

#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime>#if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif// C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector>#if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 210; struct node {int x,y; }; int dir[4][2] = {{1, 0},{-1, 0},{0, 1},{0, -1}, }; int n, m, ans; char mp[maxn][maxn]; int vis[maxn][maxn]; int step1[maxn][maxn], step2[maxn][maxn]; bool check(int x,int y) {return (x >= 0 && x < n && y >= 0 && y < m); } void BFS(node st,int step[][maxn]) {queue<node> q;q.push(st);vis[st.x][st.y] = true;while(!q.empty()){node now, next;now = q.front();q.pop();for (int i = 0; i < 4; i++){next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];if(check(next.x,next.y)&&mp[next.x][next.y]!='#'&&!vis[next.x][next.y])//最基本的条件必须符合{step[next.x][next.y] = step[now.x][now.y] + 1;vis[next.x][next.y] = true;q.push(next);}}} } int main() {int i,j;node st1, st2;while (cin >> n >> m){for (i = 0; i < n; i++){for (j = 0; j < m; j++){cin >> mp[i][j];if(mp[i][j]=='Y'){st1.x = i;st1.y = j;}if(mp[i][j]=='M'){st2.x = i;st2.y = j;}}}memset(vis, false, sizeof(vis));memset(step1, 0, sizeof(step1));BFS(st1,step1);memset(vis, false, sizeof(vis));memset(step2, 0, sizeof(step2));BFS(st2,step2);ans=INF;for (i = 0; i < n; i++)for (j = 0; j < m; j++)if (mp[i][j] == '@' && step1[i][j] != 0 && step2[i][j] != 0)if(step1[i][j]+step2[i][j]<ans)ans = step1[i][j] + step2[i][j];cout << ans * 11 << endl;}return 0; }

水平有限，有些题目方法有借鉴其他高手，如有冒犯，请联系作者进行删改。

总结

以上是生活随笔为你收集整理的基础搜索（kuangbin专题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。