西南民族大学第十二届程序设计竞赛（同步赛） A.逃出机房 (bfs)

题意:有来两个人A和B,A追B,A和B每次向上下左右移动一个单位,一共有两扇门,问A是否可以追上B(在门口追上也算合法).
题解:当时看题意说在门口也算?就觉得是判断两个人到门口的时间,对他们两个人分别跑bfs,记录他们到每个门口的步数,然后if判断一下即可.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m;

char s[20][20];

bool st[20][20];

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

int zx,zy,hx,hy;

int ex1,ey1,ex2,ey2;

int res1=INF,res2=INF,res3=INF,res4=INF;

struct misaka{

	int x,y,cnt;

}e;

void bfs1(int x,int y){

	me(st,false,sizeof(st));

	queue<misaka> q;

	int cur=0;

	q.push({x,y,0});

	while(!q.empty()){

		auto tmp=q.front();

		q.pop();

		if(st[tmp.x][tmp.y]) continue;

		st[tmp.x][tmp.y]=true;

		if(s[tmp.x][tmp.y]=='@' && cur<2){

			if(tmp.x==ex1 && tmp.y==ey1){

				res1=tmp.cnt;

			}

			else res2=tmp.cnt;

			cur++;

		}

		rep(i,0,3){

			int tx=tmp.x+dx[i];

			int ty=tmp.y+dy[i];

			if((s[tx][ty]=='*' || s[tx][ty]=='@') && !st[tx][ty]){

				q.push({tx,ty,tmp.cnt+1});

			}

		}

	}

}

void bfs2(int x,int y){

	me(st,false,sizeof(st));

	queue<misaka> q;

	int cur=0;

	q.push({x,y,0});

	while(!q.empty()){

		auto tmp=q.front();

		q.pop();

		if(st[tmp.x][tmp.y]) continue;

		st[tmp.x][tmp.y]=true;

		if(s[tmp.x][tmp.y]=='@' && cur<2){

			if(tmp.x==ex1 && tmp.y==ey1){

				res3=tmp.cnt;

			}

			else res4=tmp.cnt;

			cur++;

		}

		rep(i,0,3){

			int tx=tmp.x+dx[i];

			int ty=tmp.y+dy[i];

			if((s[tx][ty]=='*' || s[tx][ty]=='@') && !st[tx][ty]){

				q.push({tx,ty,tmp.cnt+1});

			}

		}

	}

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n>>m;

	rep(i,1,n){

		rep(j,1,m){

			cin>>s[i][j];

			if(s[i][j]=='Z') {zx=i,zy=j;}

			else if(s[i][j]=='H') {hx=i,hy=j;}

			else if(s[i][j]=='@'){

				if(!ex1 && !ey1) {ex1=i;ey1=j;}

				else {ex2=i;ey2=j;}

			}

		}

	}

	bfs1(hx,hy);

	bfs2(zx,zy);

	if(res3<res1 || res4<res2) cout<<"give me northeast chicken rice and milk tea TOMORROW!\n";

	else cout<<"give me northeast chicken rice and milk tea!\n";

    return 0;

}

巴特西

西南民族大学第十二届程序设计竞赛（同步赛） A.逃出机房 (bfs)

最新文章

热门文章