juruo求调BFS,样例都过不去
查看原帖
juruo求调BFS,样例都过不去
523541
Onana_in_XMFLS楼主2021/10/7 21:39

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const int INF = 1<<31-1;
struct Node{int x,y;};
int n,m,fx,fy,ex,ey,ans = 1;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
char a[2005][2005];
queue <Node> q;
inline void bfs()
{	
	Node start,than;
	start.x = fx;
	start.y = fy;
	q.push(start);
	while(!q.empty())
	{
		start = q.front();
		//printf("out %d %d\n",start.x,start.y);
		q.pop();
		for(int i = 0;i < 4;++i)
		{
			than.x = start.x+dx[i];
			than.y = start.y+dy[i];
			if(than.x == ex && than.y == ey) return;
			if(1 <= than.x && than.x <= n && 1 <= than.y && than.y <= m && a[than.x][than.y] == '.')
			{
				a[than.x][than.y] == '#';
				++ans;
				q.push(than);
			}
		}
	}
}
inline LL read()
{
	LL x=0,f=1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return f*x;
}
int main(int argc,char *argv[])
{
	n = read(),m = read();
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
		{
			cin>>a[i][j];
			if(a[i][j] == 'm') fx = i,fy = j;
			if(a[i][j] == 'd') ex = i,ey = j;
		}	
	//printf("%d %d\n%d %d\n",fx,fy,ex,ey);
	bfs();
	printf("%d\n",ans);
	return 0;
}
2021/10/7 21:39
加载中...