题解
当窝发现窝的锅在读入这个矩阵的时候,窝。。窝。。窝。。
果然,一遇到和字符串有关的题就开始吹空调
好啦我们说说思路吧
BFS队列实现
拿出一个没有走过的点,扩展它可以达到的节点,那么它可以到达的节点的到达时间就等于它父节点到达时间+1
代码
#include<bits/stdc++.h>
using namespace std;
const int mod=19260817;
int n,m,sx,sy,t;
long long much;
char ju[505][505];
int vis[505][505];
int dis[505][505];
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
struct node
{
int x,y;
};
queue<node>q;
int main()
{
scanf("%d%d\n",&n,&m);
memset(vis,-1,sizeof(vis));
memset(dis,0,sizeof(dis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ju[i][j]; //我的锅就在这里QWQ
if(ju[i][j]=='*')
{
sx=i;sy=j;
vis[i][j]=1;
}
if(ju[i][j]=='o')
vis[i][j]=1;
if(ju[i][j]=='#')
vis[i][j]=0;
}
node h;
h.x =sx;h.y =sy;
q.push(h);
while(!q.empty())
{
node now=q.front();
q.pop();
t=max(t,dis[now.x][now.y]);
for(int i=0;i<=3;i++)
{
int xx=now.x +dx[i];
int yy=now.y +dy[i];
if(vis[xx][yy]==0)
{
dis[xx][yy]=dis[now.x ][now.y ]+1;
vis[xx][yy]=1;
node h;
h.x =xx;
h.y =yy;
q.push(h);
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(dis[i][j]!=0)
{
dis[i][j]=t-dis[i][j]+1;
much=(much%mod+dis[i][j]%mod)%mod;
}
}
printf("%d\n",t);
printf("%ld\n",much);
return 0;
}
转载于:https://www.cnblogs.com/xiaoyezi-wink/p/11102846.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)