比赛 EYOI与SBOI开学欢乐赛1st 评测结果 AAAAAAAAAA
题目名称 拖拉机 最终得分 100
用户昵称 ZRQ 运行时间 0.559 s
代码语言 C++ 内存使用 8.79 MiB
提交时间 2022-08-29 21:14:58
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int N=1e3+10;
struct point
{
	int x,y,dis;
};
int d[4][2]={0,1,0,-1,1,0,-1,0};
int n;
int sx,sy;
int mp[N][N];
bool vis[N][N];
deque<point> q;
bool judge(int x,int y)
{
	if(x<=0||y<=0||x>1000||y>1000) return 1;
	return 0;
}
void BFS()
{
	q.push_back((point){sx,sy,0});
	while(!q.empty())
	{
		point cur=q.front();
		q.pop_front();
		if(judge(cur.x,cur.y))
		{
			printf("%d\n",cur.dis);
			return;
		}
		if(vis[cur.x][cur.y]) continue;
		vis[cur.x][cur.y]=1;
		point nxt;
		for(int i=0;i<=3;++i)
		{
			nxt.x=cur.x+d[i][0];
			nxt.y=cur.y+d[i][1];
			if(mp[nxt.x][nxt.y]==0) nxt.dis=cur.dis,q.push_front(nxt);
			else nxt.dis=cur.dis+1,q.push_back(nxt);
		}
	}
}
int main()
{
	freopen("tractor.in","r",stdin);
	freopen("tractor.out","w",stdout);
	scanf("%d%d%d",&n,&sx,&sy);
	int x,y;
	for(int i=1;i<=n;++i) scanf("%d%d",&x,&y),mp[x][y]=1;
	BFS();
	return 0;
}