社区讨论
求助!
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 条回复,欢迎继续交流。
正在加载回复...