社区讨论

求助!

AT_abc151_d [ABC151D] Maze Master参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@luc7j9r3
此快照首次捕获于
2024/03/29 13:12
2 年前
此快照最后确认于
2024/03/29 17:18
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;

#define wrap() printf("\n")
#define print(x) printf("%d",x);
typedef long long int ll;
typedef int inter;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef unsigned __int128 uint128;	
const int E = 1e6+10;
const int S = 1e7+10;
const int U = 1<<30;
const int T = 1e4*2+10;
const int F = 65540;//F = 65535 + 5
const int Q = 1010;
const long long Y = 1LL<<60LL;	
const int maxp = 1e5 + 10;

const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int h,w,ans=0,q[10000001][2],dist[1001][1001];
char a[1002][1002];

int bfs(int x,int y,int ei,int ej)
{
	memset(dist,255,sizeof(dist));
	dist[x][y] = 0;
	int front = 1,rear = 1;
	q[1][0] = x,q[1][1] = y;
	while(front <= rear)
	{
		int x = q[front][0],y = q[front][1];
		++front;
		for(int i=0;i<4;i++)
		{
			int xx = x + d[i][0],yy = y + d[i][1];
			if(xx < 1 || xx > h || yy < 1 || yy > w) continue;
			if(a[xx][yy] != '#' && dist[xx][yy] == -1)
			{
				dist[xx][yy] = dist[x][y] + 1;
				++rear;
				q[rear][0] = xx;
				q[rear][1] = yy; 
				if(dist[ei][ej] != -1)
				{
					return dist[xx][yy];
				}
			}
		}
	}
}

int main()
{ 
	scanf("%d%d",&h,&w);
	for(int i = 1;i <= h;i++)
	{
		char s[1001];
		scanf("%s",s+1);
		for(int j = 1;j <= w;j++)
		{
			a[i][j] = s[j];
		}
	}
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			for(int k=1;k<=h;k++)
			{
				for(int q=1;q<=w;q++)
				{
					if(a[i][j] != '#' && a[k][q] != '#')
					{
						ans = max(ans,bfs(i,j,k,q));
					}
				}
			}
		}
	}
	printf("%d",ans);
}

#undef wrap
#undef print	

回复

0 条回复,欢迎继续交流。

正在加载回复...