本地通过,洛谷CE?
查看原帖
本地通过,洛谷CE?
204260
jiyuanzhiguang楼主2022/8/20 10:26
/*

*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <iomanip>

using namespace std;
const int N = 1e3 + 10;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int n;
int step[N][N];
int x1, y1,x2, y2;
bool use[N][N];
int ans;
char a[N][N];

void bfs(int x, int y)
{
	queue < pair<int,int> > q;
	q.push(make_pair(x, y));
	use[x][y] = true;
	while(q.size())
	{
		int x = q.front().first;
		int y = q.front().second;
//		if(x == x1 && y == y1)
//		{
//			ans = step[x][y];
//			return;
//		}
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int bx = x + dx[i];
			int by = y + dy[i];
			if(1 <= bx && bx <= n && 1 <= by && by <= n && a[bx][by] != '1' && use[bx][by] == false)
			{
				use[bx][by] = true;
				step[bx][by] = step[x][y] + 1;
				q.push(make_pair(bx, by));
			}
		}
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> a[i][j];
	cin >> x2 >> y2 >> x1 >> y1;
	bfs(x2, y2);
	
	cout << step[x1][y1];
	return 0;
}

2022/8/20 10:26
加载中...