信息学奥赛一本通 2.8：广度优先搜索

1252 走迷宫

#include <iostream>
#include <queue>
using namespace std;

const int N = 50;
char a[N][N];
int step[N][N];
int r, c;
int dx[4] = {
   -1, 0, 1, 0};
int dy[4] = {
   0, 1, 0, -1};

struct node{
   int x, y;};
queue<node> q;

void bfs() {
   
	node point, front;
	
	point.x = 1, point.y = 1;
	q.push(point);
	step[1][1] = 1;
	
	while (q.size()) {
   
		front = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i ++ ) {
   
			int xx = front.x + dx[i];
			int yy = front.y + dy[i];
			
			if (xx < 1 || xx > r || yy < 1 || yy > c) continue;
			if (a[xx][yy] == '#') continue;
			if (step[xx][yy] != 0) continue;
			
			point.x = xx, point.y = yy;
			q.push(point);
			step[xx][yy] = step[front.x][front.y] + 1;
		}
	}
}

int main() {
   
	cin >> r >> c;
	
	for (int i = 1; i <= r; i ++) {
   
		for (int j = 1; j <= c; j ++) {
   
			cin >> a[i][j];
		}
	}

	bfs();
	
	cout << step[r][c] << endl;
	
	return 0;
}

1254 走出迷宫

#include <iostream>
#include <queue>
using namespace std;

const int N = 105;
char a[N][N];
int step[N][N];
int n, m, sx, sy, tx, ty;
int dx[4] = {
   -1, 0, 1, 0};
int dy[4] = {
   0, 1, 0, -1};

struct node{
   int x, y;};
queue<node> q;

void bfs() {
   
	node point, front;
	
	point.x = sx, point.y = sy;
	q.push(point);
	
	while (q.size()) {
   
		front = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i ++ ) {
   
			int xx = front.x + dx[i];
			int yy = front.y + dy[i];
			
			if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
			if (a[xx][yy] == '#') continue;
			if (step[xx][yy] != 0) continue;
			
			point.x = xx, point.y = yy;
			q.push(point);
			step[xx][yy] = step[front.x][front.y] + 1;
		}
	}
}

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] == 'S') sx = i, sy = j;
			if (a[i][j] == 'T') tx = i, ty = j;
		}
	}

	bfs();
	
	cout << step[tx][ty] << endl;
	
	return 0;
}

1251 仙岛求药

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 105;
char a[N][N];
int step[N][N];
int n, m, sx, sy, tx, ty;
int dx[4] = {
   -1, 0, 1, 0};
int dy[4] = {
   0, 1, 0, -1};

struct node{
   int x, y;};
queue<node> q;

void bfs() {
   
	node point, front;
	
	memset(step, -1, sizeof(step));
	point.x = sx, point.y = sy;
	q.push(point);
	step[sx][sy] = 0;
	
	while (q.size()) {
   
		front = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i ++ ) {
   
			int xx = front.x + dx[i];
			int yy = front.y + dy[i];
			
			if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
			if (a[xx][yy] == '#') continue