搜索

1、BFS 广度优先搜索

一般用于地图的搜索遍历，最短路中的SPFA也是

洛谷 P1126 机器人搬重物

<1> 对于面对方向的计算 设四个方向分别为 0， 1， 2， 3 转向的时候只需要 （原方向代号 + 4 ± 1）% 4 就可以得到转向后面对的新方向

<2>对于每种状态，构建hash，在每次走后判断该种情况是否已经出现，如果没有出现，标记为出现，反之，不继续搜索

代码：

#include<bits/stdc++.h>
using namespace std;
const int my[4] = {0, 1, 0, -1}, mx[4] = {-1, 0, 1, 0};
int n, m, maze[60][60];
bool vis[20000];
inline int fun(int a, int b, int c){return c * 2700 + a * 51 + b;};//计算对应的数值
struct pos{
	int x, y;
	int f;
	int mov;
};
queue<pos> que;
inline bool zq(int x, int y){//计算会不会与障碍物相撞
	if(maze[x][y] || maze[x + 1][y] || maze[x][y + 1] || maze[x + 1][y + 1]){
		return true;
	}
	return false;
}
inline void bfs(){
	int x, y, tx, ty, f, d, mov, lx, ly;
	char c;
	cin >> x >> y >> tx >> ty >> c;
	switch(c){
		case 'N' : f = 0;
		break;
		case 'E' : f = 1;
		break;
		case 'S' : f = 2;
		break;
		case 'W' : f = 3;
		break;
	}
	pos temp;//初始化机器人的起点
	temp.x = x, temp.y = y, temp.f = f, temp.mov = 0;
	que.push(temp);
	while(!que.empty()){
		temp = que.front();
		que.pop();
		x = temp.x, y = temp.y, f = temp.f, d = fun(x, y, f), mov = temp.mov;
		if(x == tx && y == ty){//如果到达终点，直接输出并返回
			cout << mov ;
			return;
		}
		if(vis[d]) continue;//如果该种情况已经出现过了，则不进行搜索
		vis[d] = 1;//将该种情况标记为已经出现
		temp.mov++;//步数++
		temp.f = (f + 4 - 1) % 4; que.push(temp);//左转 并放入队列中
		temp.f = (f + 4 + 1) % 4; que.push(temp);//右转 并放入队列中
		temp.f = f;//重置方向
		for(int i = 1; i <= 3; ++i){//走路
			lx = x + mx[f] * i, ly = y + my[f] * i;//计算走到的地点
			if(lx <= 0 || ly <= 0 || lx >= n || ly >= m || zq(lx, ly)) break;//如果出界，就没必要再走了
			temp.x = lx, temp.y = ly; que.push(temp);//将走到的状况放入队列中
		}	
	}
	cout << -1 << endl;//无法走到终点，输出-1
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			cin >> maze[i][j];
		}
	}
	bfs();
	return 0;
}

洛谷 P1189 SEARCH

<1>先找到出发点，将其放到q队列中，（q队列储存当前步骤能进行走的点）然后将出发点改成正常道路

<2>将q队列中的点取出，按照给定方向进行走，将得到的点放入t队列中

<3>将t队列的点放到q队列中，作为下一次操作的起始点

<4>最终得到的q队列就是结果

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
char mapp[N][N];
int r, c, w;
string ss;
bool vis[N][N];
int dx[7] = {0, -1, 0, 1, 0}, dy[7] = {0, 0, 1, 0, -1};
queue<pair<int, int>> q, t;

// 坐标和方向 
inline void dfs(int x, int y, int p){
	int tx = x + dx[p];
	int ty = y + dy[p];
	if(mapp[tx][ty] == 'X' || tx > r || tx < 1 || ty > c || ty < 1) return;
	if(vis[tx][ty] == true) return;
	vis[tx][ty] = true;
	t.push(make_pair(tx, ty));
	dfs(tx, ty, p);
}

inline void bfs(string dir){
	int fx;
	switch(dir[0]){
		case 'N' : fx = 1;
		break;
		case 'S' : fx = 3;
		break;
		case 'W' : fx = 4;
		break;
		case 'E' : fx = 2;
	}
	while(!q.empty()){
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		dfs(tx, ty, fx);
	}
	memset(vis, false, sizeof vis);
	while(!t.empty()){
		q.push(t.front());
		t.pop();
	}
}

int main(){
	cin >> r >> c;
	for(int i = 1; i <= r; ++i){
		for(int j = 1; j <= c; ++j){
			cin >> mapp[i][j];
			if(mapp[i][j] == '*'){
				q.push(make_pair(i, j));
				mapp[i][j] = '.';
			}
		}
	}
	cin >> w;
	for(int i = 1; i <= w; ++i){
		cin >> ss;
		bfs(ss);
	}
	while(!q.empty()){
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		mapp[tx][ty] = '*';
	}
	for(int i = 1; i <= r; ++i){
		for(int j = 1; j <= c; ++j){
			cout << mapp[i][j];
		}
		cout << endl;
	}
	return 0;
}