走迷宫题目

如果是求最短路径则用bfs

#include<iostream>
#include<vector>
#include <queue>
#include <array>
using namespace std;
class solution {
public:
	int bfs(vector<vector<char>>& grid, int x, int y) {
		int n = grid.size();
		int m = grid[0].size();
		vector<vector<bool>> vis(n, vector<bool>(m, false));
		vector<vector<int>> f(n, vector<int>(m, 0));
		queue<pair<int, int>> q;
		q.push({ x,y });
		while (!q.empty()) {
			int rx = q.front().first;
			int ry = q.front().second;
			q.pop();
			for (int k = 0; k < 4; k++) {
				int nx = rx + dx[k];
				int ny = ry + dy[k];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 'e') {
					return f[rx][ry] + 1;
				}
				if ( nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.'&&!vis[nx][ny]) {
					vis[nx][ny] = true;
					f[nx][ny] = f[rx][ry] + 1;
					q.push({ nx,ny });
				}
			}
		}
		return -1;
	}


	array<int, 4> dx = { -1,0,1,0 };
	array<int, 4> dy = { 0,1,0,-1 };


};
int main() {
	int n, m;
	cin >> n >> m;
	int x, y;
	vector<vector<char>> grid(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 's') {
				x = i;
				y = j;
			}
		}
	}
	cout <<solution().bfs(grid, x, y);




}

如果是求方案数，用回溯+dfs