网格最短路宽搜求调
  • 板块灌水区
  • 楼主Manki23333333
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/5/31 19:17
  • 上次更新2023/10/23 14:13:55
查看原帖
网格最短路宽搜求调
871004
Manki23333333楼主2023/5/31 19:17

没有输出捏

#include <bits/stdc++.h> 
using namespace std;
#define int long long
struct NODE{
	int x, y, step;
};
const int maxn = 1005 * 1005 * 2;
NODE q[2010];
int sx, sy, ex, ey, head = 0, tail = 1, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}, n , m;
bool g[1005][1005], flag[1005][1005];
void bfs(){
	q[1].x = sx - 1;
	q[1].y = sy - 1;
	q[1].step = 0;
	flag[sx][sy] = true;
	while(head <= tail){
		int ux = q[head].x, uy = q[head].y;
		if (ux == (ex - 1) && uy == (ey - 1)){
			cout << q[tail].step;
		}
		for (int i = 0; i < 4; i ++){
			int nx = dx[i] + ux, ny = dy[i] + uy;
			if (flag[nx][ny] || nx < 0 || nx > n || ny < 0 || ny > m || g[nx][ny]) continue;
			q[++tail].x = nx;
			q[tail].y = ny;
			q[tail].step = q[head].step + 1;
			flag[nx][ny] = true;
		}
		head ++;
	}
}
signed main(){		
	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m ; j ++)
			cin >> g[i][j];
	cin >> sx >> sy >> ex >> sy;
	bfs();
	return 0;
}
2023/5/31 19:17
加载中...