bfs板子题TLE求助
查看原帖
bfs板子题TLE求助
649751
Blued楼主2023/3/28 19:19
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 55;

int n , m;

bool a[N][N];

int x_sta , y_sta , x_end , y_end;

char ch;

int ans = LONG_LONG_MAX;

int dx[4] = {-1 , 1 , 0 , 0};

int dy[4] = {0 , 0 , -1 , 1};

bool vis[N][N];

struct qw
{
	int x , y , num;
};

queue < qw > q;

void bfs(int x , int y , int num)
{
	q.push(qw{x , y , num});
	
	while(! q.empty())
	{
		x = q.front().x , y = q.front().y , num = q.front().num;
		q.pop();
		vis[x][y] = true;
		
		if(x == x_end && y == y_end)
			ans = min(num , ans);
		
		for(int i = 0;i < 4;i ++)
			if(x + dx[i] >= 1 && x + dx[i] <= n && y + dy[i] >= 1 && y + dy[i] <= m)
				if(a[x + dx[i]][y + dy[i]] && ! vis[x + dx[i]][y + dy[i]])
					q.push(qw{x + dx[i] , y + dy[i] , num + 1});
	}
	
	return ;
}

main()
{
	cin >> n >> m;
	
	cin >> x_sta >> y_sta >> x_end >> y_end;
	
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= m;j ++)
			cin >> ch , a[i][j] = ch == '.' ? 1 : 0;
	
	bfs(x_sta , y_sta , 0);
	
	cout << ans << '\n';
}
2023/3/28 19:19
加载中...