1256：献给阿尔吉侬的花束--BFS多组输入--memset

题目

解析

标准的BFS题目，在多组输入中要做的就是先找到这一组的起点和终点，然后将其传给bfs，在多组输入中最易忘记的是将数组“归零”【即memset】

代码【结构体】

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int t, r, c;
char map[210][210];
int book[210][210];int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};//定义结构体用于存储坐标
struct node {int x, y, step;
};//BFS模板
void bfs(int sx, int sy, int ex, int ey) {memset(book, 0, sizeof book); //注意：这种多组输入的题目，一定要memset！！！.QAQqueue<node> q;q.push({sx, sy, 0});book[sx][sy] = 1;//标记起点while (!q.empty()) {node s = q.front();q.pop();//移动for (int i = 0; i < 4; i++) {int nx = s.x + dx[i], ny = s.y + dy[i];//判定是否满足条件if (nx >= 0 && ny >= 0 && nx < r && ny < c && !book[nx][ny] && map[nx][ny] == '.') {book[nx][ny] = 1;//标记走过的值q.push({nx, ny, s.step + 1}); //传新坐标和步数}//如果到达目标点，则输出步数if (nx == ex && ny == ey) {cout << s.step + 1;return;}}}cout << "oop!";
}int main() {cin >> t;
//多组输入模板while (t--) {int sx, sy, ex, ey;cin >> r >> c;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {cin >> map[i][j];if (map[i][j] == 'S') {sx = i;sy = j;} else if (map[i][j] == 'E') {ex = i;ey = j;}}}bfs(sx, sy, ex, ey);}return 0;
}

用book标记且计步数的代码[非结构体法]

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int t, r, c;char map[210][210];
int book[210][210];
typedef pair<int, int> PII;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};void bfs(int sx, int sy, int ex, int ey) {memset(book, 0, sizeof book);book[sx][sy]=1;queue<PII> q;q.push({sx, sy});while (!q.empty()) {PII top = q.front();q.pop();for (int i = 0; i < 4; i++) {int nx = top.first + dx[i], ny = top.second + dy[i];if (nx >= 0 && ny >= 0 && nx < r && ny < c && !book[nx][ny] && map[nx][ny] != '#') {book[nx][ny] += book[top.first][top.second] + 1;//用book标记且计步数q.push({nx, ny});if (nx == ex && ny == ey) {cout << book[nx][ny] << endl;return;}}}}cout << "oop!" << endl;}int main() {cin >> t;while (t--) {cin >> r >> c;int sx, sy, ex, ey;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {cin >> map[i][j];if (map[i][j] == 'S')sx = i, sy = j;if (map[i][j] == 'E')ex = i, ey = j;}}bfs(sx, sy, ex, ey);}return 0;
}