BFS能否到达问题

#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int n, m;
bool flg, vis[N][N];
char a[N][N];

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

struct node {
	int x, y;
};

void bfs() {
	queue<node> q;  // 起点入队
	q.push({1, 1});
	vis[1][1] = 1;
	// 从队列取点拓展
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		// 是不是终点
		if (x == n && y == m) {
			flg = 1;
			return ;
		}
		// 拓展四个方向
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			// 判断越界
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			// 判断是否能走
			if (a[nx][ny] == '#')
				continue;
			// 判断是否走过
			if (vis[nx][ny])
				continue;
			vis[nx][ny] = 1;
			q.push({nx, ny});
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	bfs();
	if (flg == 1)
		cout << "YES";
	else
		cout << "NO";
	return 0;
}

迷宫2

#include <bits/stdc++.h>
using namespace std;
const int N = 50;

struct node {
	int x, y, t;
};
char a[N][N];
bool flg = 1, vis[N][N];

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};
int men[12][2], cnt;

void  bfs() {
	queue<node> q;
	vis[1] = 1;
	q.push({1, 1, 1});
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int t = q.front().t;
		q.pop();
		// 判断是不是终点
		if (x == n && y == m) {
			cout << t;
			return;
		}
		// 判断是不是门
		if (a[x][y] == '$') {
			// 得到所有的门，全部走
			for (int i = 1; i <= cnt; i++) {
				if (vis[men[i][0]][men[i][1]])
					break;
				vis[men[i][0]][men[i][1]] = 1;
				q.push(men[i][0], men[i][1], t);   // 所有的门入队
			}
		}
		// 拓展
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == '$') {
				cnt++; // 处理得到所有的门
				men[cnt][0] = i;
				men[cnt][1] = j;
			}
		}
	bfs();
	if (flg)
		cout << -1;
	return 0;
}

迷宫3

#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, m, dis[N][N];
char a[N][N];
int sx, sy, fx, fy;
bool flg = 1;

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

struct node {
	int x, y, t;
	// C++ 11 重载运算符 , 优先队列里面每次出小的
	bool operator < (node a) {
		return t > a.t;
	}
};

void bfs() {
	memset(dis, 0x3f, sizeof(dis));
	dis[sx][sy] = 0;
	priority_queue<node> q;
	q.push({sx, sy, 0});
	// 不能直接判断出口？？？？？？
	// 没办法保证第一次到这个点是最优的
	// 能解决保证第一个到这个点是最优的，可以直接判断出口
	// 每次都取最短时间去扩展，    queueu , priority_queue
	//  priority_queue  默认是大根堆，优先出大的
	// (x1,y1)  (x2,y2)   同时去拓展 到 (xx,yy) ,(xx,yy)花费固定
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int t = q.front().t;
		q.pop();
		// 判断终点
		if (x == fx && y == fy) {
			cout << t;
			flg = 0;
			return ;
		}
		// 拓展

	}
}

int main() {
	cin >> n >> m;
	// 输入
	bfs();
	//  输出
	if (flg)
		cout << "IMPOSSIBLE";
	return 0;
}

BFS联通块

void bfs(int x, int y) {
	q.push({x, y});
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		// 遍历四个方向
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
			if (vis[nx][ny]) continue;
			if (a[nx][ny]) continue;
			vis[nx][ny] = 1;
			q.push({nx, ny});
		}
	}
}

字串变换

// vis数组判断点是否访问过
// 怎么判断字符串是否访问过
// 映射，vis[类型] = 1;
// map<string , bool > vis;
#include <bits/stdc++.h>
using namespace std;

void bfs() {
	// 字符串， 变换次数
	queue<pair<string, int> > q;
	q.push(make_pair(A, 0));
	while (!q.empty()) {

		// 变换规则
		// 遍历所有的规则，看是否能变换
		for (int i = 0; i < n; i++) {
			// 能变换的前提是字符串里面能找到 a[i]
			// 每次尝试变换的起点都是 s , 所以 s 的值不能改变
			string now = s;
			while (1) {
				int p = now.find(a[i]);
				if (p == -1)
					break;
				// 找到
				string tmp = s;
				tmp.replace(p, a[i].size(), b[i]);
				q.push(make_pair(tmp, t + 1));
				now[p] = ' ';
			}
		}
	}
}

int main() {
	return 0;
}

机器人搬重物

// 机器人只能在格子的点上走
// 机器人不能超越出去
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m, a[N][N], sx, sy, ex, ey, sd, dis[N][N][4];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int Get(char x) {
	if (x == 'N') return 0;
	if (x == 'S') return 2;
	if (x == 'E') return 1;
	if (x == 'W') return 3;
}
struct node {
	int x, y, dir, cost;
	friend bool operator <(node a, node b) {
		return a.cost > b.cost;
	}
};
priority_queue<node>q;
void bfs() {
	memset(dis, 0x3f, sizeof(dis));
	q.push({sx, sy, sd, 0});
	dis[sx][sy][sd] = 0;
	while (!q.empty()) {
		node tmp = q.top();
		q.pop();
		int x = tmp.x;
		int y = tmp.y;
		int dir = tmp.dir;
		int Dir = (dir + 1) % 4; // 转弯，向右或者向左都行，一个分配一个方向
		if (dis[x][y][Dir] > tmp.cost + 1) {
			dis[x][y][Dir] = tmp.cost + 1;
			q.push({x, y, Dir, tmp.cost + 1});
		}
		Dir = (dir + 3) % 4; // // 转弯，向右或者向左都行，一个分配一个方向
		if (dis[x][y][Dir] > tmp.cost + 1) {
			dis[x][y][Dir] = tmp.cost + 1;
			q.push({x, y, Dir, tmp.cost + 1});
		}
		int xx = x, yy = y;
		// 走1 - 3 个步骤的时候，如果不能走1，那2肯定也不能
		// 同理如果2不能，那么3肯定也不能
		for (int j = 1; j <= 3; j++) { // 走 1 - 3 步骤
			xx += dx[dir];
			yy += dy[dir];
			// 在范围内
			if (xx >= 1 && xx + 1 <= n && yy >= 1 && yy + 1 <= m) {
				// 走到的点的四周没有不能走的点
				if (a[xx][yy] != 1 && a[xx][yy + 1] != 1 && a[xx + 1][yy] != 1 && a[xx + 1][yy + 1] != 1) {
					if (dis[xx][yy][dir] > tmp.cost + 1) {
						dis[xx][yy][dir] = tmp.cost + 1;
						q.push({xx, yy, dir, tmp.cost + 1});
					}
				} else break;
			} else break;
		}
	}
	int ans = 0x3f3f3f3f;
	for (int i = 0; i < 4; i++) {
		ans = min(ans, dis[ex][ey][i]);
	}
	if (ans == 0x3f3f3f3f) cout << -1 << endl;
	else cout << ans << endl;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	cin >> sx >> sy >> ex >> ey;
	char x;
	cin >> x;
	sd = Get(x);
	bfs();
	return 0;
}