40分bfs求助
  • 板块P1605 迷宫
  • 楼主Ethereal_GG
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/2/1 10:03
  • 上次更新2023/10/24 02:16:35
查看原帖
40分bfs求助
600706
Ethereal_GG楼主2023/2/1 10:03
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n , m;
int t;
int stax , stay;
int tarx , tary;
bool vis[1009][1009];
int step[1009][1009];
queue<pair<int , int>> q;
int fx[] = {0 , -1 , 1 , 0 , 0};
int fy[] = {0 , 0 , 0 , -1 , 1};
int g[1009][1009];
int ans;
void bfs(int x , int y){
	vis[x][y] = true;
	step[x][y] = 0;
	q.push(make_pair(x , y));
	while(!q.empty()){
		int nx = q.front().first;
		int ny = q.front().second;
		if(nx == tarx && ny == tary) ans++;
		q.pop();
		for(int i = 1;i <= 4;i++){
			int newx = nx + fx[i];
			int newy = ny + fy[i];
			if(newx >= 1 && newx <= tarx && newy >= 1 && newy <= tary && !vis[newx][newy]){
				vis[newx][newy] = true;
				step[newx][newy] = step[nx][ny] + 1;
				q.push(make_pair(newx , newy));
			}
		}
	}
	cout << ans << endl;
}
int main(){
	cin >> n >> m;
	cin >> t;
	cin >> stax >> stay;
	cin >> tarx >> tary;
	vis[stax][stay] = 1;
	for(int i = 1;i <= t;i++){
		int vx , vy;
		cin >> vx >> vy;
		vis[vx][vy] = true;
	} 
	bfs(stax , stay);
	return 0;
}
2023/2/1 10:03
加载中...