bfs 最短路径有几条

题意

样例输入：
4
...S
.XX.
.XX.
E...
样例输出：
6
2
数据范围：
1 ≤n ≤ 25

解析

path数组记录点

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
const int inf = 0x3f3f3f3f; 
char a[N][N];
int n,sx,sy,ex,ey;
int vis[N][N],path[N][N];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
struct node{
	int x,y;
};
queue<node> q;
void bfs(){
	vis[sx][sy] = 0;
	path[sx][sy] = 1;
	q.push({sx,sy});
	while(q.size()){
		node t = q.front();
		q.pop();
		if(t.x == ex && t.y == ey) return;//
		for(int i=0;i<4;i++){
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
			if(a[nx][ny] == 'X') continue;
			if(vis[nx][ny] != inf){
				path[nx][ny] += path[t.x][t.y];
				continue;
			}
			vis[nx][ny] = vis[t.x][t.y] + 1;
			path[nx][ny] = path[t.x][t.y];
			q.push({nx,ny});
		} 
	}
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin >> a[i][j];
			if(a[i][j] == 'S') sx = i,sy = j;
			if(a[i][j] == 'E') ex = i,ey = j;
		}
		
	}
	memset(vis,0x3f,sizeof vis);
	bfs();
	printf("%d\n%d",vis[ex][ey],path[ex][ey]);
	return 0;
}