目录
浅谈搜索:
深度优先搜索（Depth-First Search）和广度优先搜索 BFS ( Breadth-First Search )
是基本的暴力技术 ，常用与解决图和树的遍历问题。
BFS 常与queue、priority_queue配合使用，可以解决最短路径问题、迷宫问题
priority_queue + bfs
1、
kun倒是有一项特异功能——可以破坏障碍物。假设kun在一个N*M的迷宫中，"."代表可以通过的空地，"*"代表可以破坏的障碍物，"#"代表不可破坏的障碍物。问kun至少要使用多少次特异功能才可逃出迷宫？
"@"代表kun的位置。小昆虫每次可以向上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。
// priority_queue + bfs
#include<bits/stdc++.h>
using namespace std;
const int Max = 1005;
int n, m;
char mp[Max][Max]{};
bool vis[Max][Max]{};
struct node{
int x, y, num;
friend bool operator < (const node&a,const node&b){
return a.num > b.num;
}
};
bool judge(int x,int y){
if(x==1||x==n||y==1||y==m)
return true;
return false;
}
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool check(int x,int y){
if(mp[x][y]=='#'||vis[x][y])
return false;
return true;
}
int bfs(int x,int y,int num){
if(judge(x,y)){
return 0;
}
priority_queue<node> q;
q.push({x, y, 0});
vis[x][y] = true;
while(!q.empty()){
x = q.top().x;
y = q.top().y;
num = q.top().num;
if(judge(x,y)){
return num;
}
q.pop();
for (int i = 0; i < 4;++i){
int dx = x + dir[i][0];
int dy = y + dir[i][1];
// 能走
if(check(dx,dy)){
if(mp[dx][dy]=='*'){
q.push({dx, dy, num + 1});
//cout << dx << " " << dy << " " << num + 1 << endl;
}
else{
q.push({dx, dy, num});
//cout << dx << " " << dy << " " << num + 1 << endl;
}
vis[dx][dy] = true;
}
}
}
return -1;
}
int main(){
int t;
cin >> t;
while(t--){
memset(vis, false, sizeof(vis));
cin >> n >> m;
int x, y;
for (int i = 1; i <= n;++i)
for (int j = 1; j <= m;++j){
cin >> mp[i][j];
if(mp[i][j]=='@'){
x = i, y = j;
}
}
int ans = bfs(x, y, 0);
cout << ans << endl;
}
//system("pause");
return 0;
}2、
小波又脑补出了一个新的迷宫游戏。现有一大小为x*y*z三维迷宫，告诉你王子和公主的位置，王子每次可以向他的六个方向走一步（即：前、后、左、右、上、下）。迷宫中存在一些墙壁（用'#'表示），同时还存在一些陷阱（用'*'表示，在这个游戏中，王子每经过一次陷阱，则会掉一滴血，但是不会消耗时间），正常可以行走的路用'.'表示，王子的位置用'S'表示，公主的位置用'E'表示。假设初始时，王子有n滴血，现在问王子在保证血量大于0的情况下，最快需要走多少步才能营救公主（当然王子足够聪明，不会回头路），如果不能则输出"No solution"。
// 优先队列 + bfs + 3维方向
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Max = 105;
int x, y, z, n;
char mp[Max][Max][Max]{};
bool vis[Max][Max][Max]{};
struct node{
// 结构体内变量定义的顺序 非常重要
// 谁叫你喜欢 直接push
int x, y, z, dis, blood;
friend bool operator <(const node&a,const node&b){
return a.dis > b.dis;
}
};
priority_queue<node> q;
// 6个方向， 每个方向(x,y,z)
int dir[6][3] = {1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1};
bool check(int dx,int dy,int dz){
if(dx<1||dx>x||dy<1||dy>y||dz<1||dz>z||vis[dz][dx][dy]||mp[dz][dx][dy]=='#')
return false;
return true;
}
int bfs(int x,int y,int z,int dis,int blood){
// 起始点的 x,y,z,dis,blood 只会用到一次，所以 后面可以 废物利用
while(!q.empty())
q.pop();
q.push({x, y, z, dis, blood});
// 请注意： vis 和 mp 中的 z表示的是层，x表示的是行，y表示的是列
vis[z][x][y] = true;
while(!q.empty()){
x = q.top().x;
y = q.top().y;
z = q.top().z;
blood = q.top().blood;
dis = q.top().dis;
if(mp[z][x][y]=='E'){
return dis;
}
// 记得要 pop 掉，要不然陷入死循环
q.pop();
for (int i = 0; i < 6;++i){
int dx = x + dir[i][0];
int dy = y + dir[i][1];
int dz = z + dir[i][2];
if(check(dx,dy,dz)){
if(mp[dz][dx][dy]=='*'){
if(blood>1){
q.push({dx, dy, dz, dis + 1, blood - 1}); //注意打印的时候 dis 后面要加1，才是正确的步数
//cout << dz << " " << dx << " " << dy << " " << dis + 1 << endl;
vis[dz][dx][dy] = true;
}
}
else{
q.push({dx, dy, dz, dis + 1, blood});
//cout << dz << " " << dx << " " << dy << " " << dis + 1 << endl;
vis[dz][dx][dy] = true;
}
}
}
}
return -1;
}
int main(){
while(cin>>x>>y>>z>>n){
int dx, dy, dz;
for (int i = 1; i <= z;++i){
for (int j = 1; j <= x;++j)
for (int k = 1; k <= y;++k){
cin >> mp[i][j][k];
if(mp[i][j][k]=='S')
dz = i, dx = j, dy = k;
}
}
// dx,dy,dz 是起始点的坐标 dis: 0 blood:n
int ans = bfs(dx, dy, dz, 0, n);
if(ans==-1)
cout << "No solution" << endl;
else
cout << ans << endl;
}
//system("pause");
return 0;
}
简单的图论问题？
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int mp[N][N]{};
bool vis1[N][N]{};
// 4个方向，虽然说一个格子可以走多次，但 最多只能从上下左右进这个格子一次
// 防止反复横跳
bool vis2[N][N][4]{};
int n, m;
struct node{
int x, y, dis;
int dir;
};
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };
bool check1(int x,int y) {
if (x<1 || x>n || y<1 || y>m || vis1[x][y]||mp[x][y]==0)return false;
return true;
}
bool check2(int x, int y,int dir) {
if (x<1 || x>n || y<1 || y>m || vis2[x][y][dir] || mp[x][y] == 0)return false;
return true;
}
//辅助优先队列
bool operator<(const node& a, const node& b) {
// >：队列内元素按从小到大排序
// <：队列内元素按从大到小排序
return a.dis > b.dis;
}
int bfs1(int r1,int c1,int r2,int c2) {
if (r1 == r2 && c1 == c2)return 0;
memset(vis1, false, sizeof(vis1));
priority_queue<node>q;
q.push({r1,c1,mp[r1][c1]});
while (!q.empty())
{
int x = q.top().x;
int y = q.top().y;
int dis = q.top().dis;
if (x == r2 && y == c2)return dis;
q.pop();
for (int i = 0; i < 4; ++i) {
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if (check1(dx, dy)) {
q.push({ dx,dy,dis + mp[dx][dy] });
vis1[dx][dy] = true;
}
}
}
return -1;
}
int bfs2(int r1, int c1, int r2, int c2) {
if (r1 == r2 && c1 == c2)return 0;
memset(vis2, false, sizeof(vis2));
priority_queue<node>q;
q.push({ r1,c1,mp[r1][c1],-1 });
while (!q.empty()) {
int x = q.top().x;
int y = q.top().y;
int dis = q.top().dis;
int direction = q.top().dir;
if (x == r2 && y == c2)return dis;
q.pop();
for (int i = 0; i < 4; ++i) {
if (direction == i)continue;
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if (check2(dx, dy, i)) {
q.push({ dx,dy,dis + mp[dx][dy],i });
//i 这个方向已经来过了
vis2[dx][dy][i] = true;
}
}
}
return -1;
}
int main() {
//案例数
int c = 0;
while (cin >> n >> m) {
c++;
int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char ch[5];
scanf("%s", ch);
if (ch[0] == '*')mp[i][j] = 0;
//atoi:把字符串转化为整型
else mp[i][j] = atoi(ch);
}
}
int res1 = bfs1(r1, c1, r2, c2);
int res2 = bfs2(r1, c1, r2, c2);
cout << "Case " << c << ": " << res1 << " " << res2 << endl;
}
return 0;
}2、
线性搜索
例题1：
玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串（2=<N<=13），该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。
利用容器 set 来进行判重操作
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
string str;
int num;
node(string a, int b) {
str = a;
num = b;
}
};
bool check(string str) {
if (str.find("2012") != str.npos)return true;
return false;
}
queue<node>q;
set<string>s;
void bfs(string str,int num) {
q.push({ str,num });
s.insert(str);
while (!q.empty()) {
string a = q.front().str;
int b = q.front().num;
q.pop();
if (check(a)) {
cout << b << endl;
return;
}
int len = a.size() - 1;
for (int i = 0; i <= len - 1; ++i) {
swap(a[i], a[i + 1]);
if (s.find(a) == s.end()) {
s.insert(a);
q.push({ a,b + 1 });
}
swap(a[i], a[i + 1]);
}
}
cout << -1 << endl;
return;
}
int main() {
int n;
while (cin >> n) {
while (!q.empty())q.pop();
if (!s.empty())s.clear();
string str; cin >> str;
bfs(str, 0);
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
struct node{
int pos, t;
friend bool operator < (const node&a,const node&b){
return a.t > b.t;
}
};
priority_queue<node> q;
const int Max = 100000;
bool vis[Max+5]{};
// 优先队列 + bfs
void bfs(int n,int k,int t){
q.push({n,t});
while(!q.empty()){
int pos = q.top().pos;
int t = q.top().t;
if(pos==k){
cout << t << endl;
return;
}
q.pop();
// 把能走的情况都走一遍，都是以 t+1 的时间为代价呀
// 而且，走过的，都标记一下
if(pos-1>=0&&!vis[pos-1]){
q.push({pos - 1, t + 1});
}
if(pos+1<=Max&&!vis[pos+1]){
q.push({pos + 1, t + 1});
}
if(pos*2<=Max&&!vis[pos*2]){
q.push({pos * 2, t + 1});
}
}
}
int main(){
int n, k;
while(cin >> n >> k){
if(n>k)
cout << k - n << endl;
else{
bfs(n,k,0);
}
}
return 0;
}