C++(g++ 7.5.0) 解法, 执行用时: 2768ms, 内存消耗: 14908K, 提交时间: 2022-09-22 23:57:56
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<string> s(n+5);
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=' '+s[i];
}
auto hs=[&](int x,int y)
{
return (x-1)*m+y;
};
const array<int,8> dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1};
auto inbounds=[&](int x,int y)
{
return 1<=x and x<=n and 1<=y and y<=m;
};
auto cal=[&](int t,int fl=0)
{
vector<vector<int>> dis(n+5,vector<int>(m+5,1e9)),col(n+5,vector<int>(m+5));
queue<pair<int,int>> q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='*')
{
dis[i][j]=0;
col[i][j]=hs(i,j);
if(dis[i][j]<t)q.emplace(i,j);
}
}
}
while(not q.empty())
{
auto [x,y]=q.front();q.pop();
for(int d=0;d<4;d++)
{
if(inbounds(x+dx[d],y+dy[d]) and s[x+dx[d]][y+dy[d]]!='#' and dis[x+dx[d]][y+dy[d]]>dis[x][y]+1)
{
dis[x+dx[d]][y+dy[d]]=dis[x][y]+1;
col[x+dx[d]][y+dy[d]]=col[x][y];
if(dis[x+dx[d]][y+dy[d]]<t)q.emplace(x+dx[d],y+dy[d]);
}
}
}
if(fl)
{
fill(dis.begin(),dis.end(),vector<int>(m+5,1e9));
const int lim=n+m;
vector<queue<pair<int,int>>> pq(lim+5);
for(int i=1;i<=n;i++)
{
if(s[i][1]=='#')
{
dis[i][1]=0;
pq[0].emplace(i,1);
}
else if(col[i][1])
{
dis[i][1]=1;
pq[1].emplace(i,1);
}
}
for(int i=1;i<=m;i++)
{
if(s[n][i]=='#')
{
dis[n][i]=0;
pq[0].emplace(n,i);
}
else if(col[n][i])
{
dis[n][i]=1;
pq[1].emplace(n,i);
}
}
int cd=0;
while(cd<=lim)
{
while(pq[cd].empty() and cd<=lim)cd++;
if(cd>lim)break;
auto [x,y]=pq[cd].front();pq[cd].pop();
if(dis[x][y]!=cd)continue;
for(int d=0;d<8;d++)
{
int xx=x+dx[d],yy=y+dy[d];
if(inbounds(xx,yy) and (s[xx][yy]=='#' or col[xx][yy]))
{
int del;
if(s[xx][yy]=='#' and s[x][y]=='#')del=0;
else if(s[xx][yy]=='#' or s[x][y]=='#')del=1;
else if(col[xx][yy]==col[x][y])del=0;
else del=2;
if(dis[xx][yy]>dis[x][y]+del)
{
dis[xx][yy]=dis[x][y]+del;
pq[dis[xx][yy]].emplace(xx,yy);
}
}
}
}
int ans=1e9;
for(int i=1;i<=n;i++)
{
if(s[i][m]=='#')
ans=min(ans,dis[i][m]);
else if(col[i][m])
ans=min(ans,dis[i][m]+1);
}
for(int i=1;i<=m;i++)
{
if(s[1][i]=='#')
ans=min(ans,dis[1][i]);
else if(col[1][i])
ans=min(ans,dis[1][i]+1);
}
return ans/2;
}
else
{
fill(dis.begin(),dis.end(),vector<int>(m+5,1e9));
queue<pair<int,int>> q;
for(int i=1;i<=n;i++)
{
if(s[i][1]=='#' or col[i][1])
{
dis[i][1]=0;
q.emplace(i,1);
}
}
for(int i=1;i<=m;i++)
{
if(s[n][i]=='#' or col[n][i])
{
dis[n][i]=0;
q.emplace(n,i);
}
}
while(not q.empty())
{
auto [x,y]=q.front();q.pop();
for(int d=0;d<8;d++)
{
int xx=x+dx[d],yy=y+dy[d];
if(inbounds(xx,yy) and (s[xx][yy]=='#' or col[xx][yy]))
{
int del=0;
if(dis[xx][yy]>dis[x][y]+del)
{
dis[xx][yy]=dis[x][y]+del;
q.emplace(xx,yy);
}
}
}
}
int ans=1e9;
for(int i=1;i<=n;i++)
{
if(s[i][m]=='#')
ans=min(ans,dis[i][m]);
else if(col[i][m])
ans=min(ans,dis[i][m]+1);
}
for(int i=1;i<=m;i++)
{
if(s[1][i]=='#')
ans=min(ans,dis[1][i]);
else if(col[1][i])
ans=min(ans,dis[1][i]+1);
}
return ans/2;
}
};
int l=0,r=n*m;
while(l<r)
{
int mid=(l+r)/2;
if(cal(mid)<=n*m)r=mid;
else l=mid+1;
}
if(l!=n*m)cout<<l<<' '<<cal(l,1)<<endl;
else cout<<-1<<endl;
return 0;
}
三种字符组成的大小为 
的方格图，其中 
代表空格（空格可以被占据）、
代表城墙（城墙不可被通过）、
代表一个普通骑士，初始时每个普通骑士都单独占据了地图上自己所在的那一个格子。 )
的格子）向位于右下角（既编号为 )
的格字）的村庄侵蚀过去（通过相邻且可以到达的格子），魔王的侵蚀速度可以认为是无穷大（瞬间即可到达（如果可以到达的话））的，魔王可以通过普通骑士所占据的格子但是不能通过被圣光骑士所占据的格子。 。
。