CodeForces CF877D题解(BFS+STL-set)

解法\(1:\)

正常的\(bfs\)剪枝是\(\Theta(nm4k)\)，这个时间复杂度是只加一个\(vis\)记录的剪枝的，只能保证每个点只进队一次，并不能做到其他的减少时间，所以理论上是过不了的。\(n*m*4*k=4*10^9\)。

这里提供一个\(codeforces\)的官方解法：\(STL-set\)优化\(bfs\)。使用\(set\)主要是能够快速找到当前行和列有那个点没有被找到过，每行每列单独建立一个\(set\)，\(set<int>\ line[N],col[N]\)。

在\(bfs\)的时候\(set<int>::iterator\ it=line[x].lower\_bound(y)\)找两次，分别处理左边和右边的答案。

再\(set<int>::iterator\ it=col[y].lower\_bound(x)\)，分别处理上下方向的答案。

细节在代码里。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
set<int> lin[N],col[N];
int n,m,k;
char mp[N][N];
int sx,sy,ex,ey;
queue<pair<int,pair<int,int> > > q;
int read()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while (c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
void add_to_que(int x,int y,int dis)
{
q.push(make_pair(dis,make_pair(x,y)));
lin[x].erase(y);
col[y].erase(x);
}
void BFS()
{
//int x1=read(),y=read()
add_to_que(sx,sy,0);
while (!q.empty())
{
int curx=q.front().second.first;
int cury=q.front().second.second;
int curd=q.front().first;
q.pop(); if(curx==ex && cury==ey)
{
printf("%d\n",curd);
exit(0);
}
set<int>::iterator wsy=lin[curx].lower_bound(cury); while (wsy!=lin[curx].end() && *wsy-cury<=k && mp[curx][*wsy]!='#')
{
add_to_que(curx,*wsy,curd+1);
wsy=lin[curx].lower_bound(cury);
}
wsy=lin[curx].lower_bound(cury);
while (wsy!=lin[curx].begin() && cury-*(--wsy)<=k && mp[curx][*wsy]!='#')
{
add_to_que(curx,*wsy,curd+1);
wsy=lin[curx].lower_bound(cury);
} wsy=col[cury].lower_bound(curx);
while (wsy!=col[cury].end() && *wsy-curx<=k && mp[*wsy][cury]!='#')
{
add_to_que(*wsy,cury,curd+1);
wsy=col[cury].lower_bound(curx);
}
wsy=col[cury].lower_bound(curx);
while (wsy!=col[cury].begin() && curx-*(--wsy)<=k && mp[*wsy][cury]!='#')
{
add_to_que(*wsy,cury,curd+1);
wsy=col[cury].lower_bound(curx);
}
}
puts("-1");
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j],lin[i].insert(j),col[j].insert(i);
sx=read(),sy=read(),ex=read(),ey=read();
BFS();
return 0;
}


解法\(2:\)

卢神发现的一个\(\Theta(nm)\)的算法\((\)我也不知道是不是这个复杂度\()\)。

每次找一个点的时候，如果在更新答案时发现当前这个新的答案不比之前的更优的话，就直接\(break\)，是的，直接退出循环。

为什么这样是对的呢？如果答案是从同一条路上来的，那么显然将来的答案不会更优。如果是拐弯过来的，那么显然按照之前的走更优。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while (c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int N=1005,inf=0x3f3f3f3f3f3f3f3f;
int n,m,k,sx,sy,ex,ey,dis[N][N],ans;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
char ch[N][N];
queue<pair<int,int> >q;
int dij()
{
memset(dis,0x3f,sizeof(dis));
q.push(make_pair(sx,sy));
dis[sx][sy]=0;
while(!q.empty())
{
int x=q.front().first,y=q.front().second; q.pop();
for(int i=0;i<4;i++)
{
for(int j=1;j<=k;j++)
{
int nx=x+dx[i]*j,ny=y+dy[i]*j;
if(nx<1 || nx>n || ny<1 || ny>m || ch[nx][ny]=='#' || dis[nx][ny]<dis[x][y]+1) break;
if(dis[nx][ny]==inf)
{
dis[nx][ny]=dis[x][y]+1;
q.push(make_pair(nx,ny));
}
}
}
}
return dis[ex][ey];
}
signed main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++) scanf("%s",ch[i]+1);
sx=read(),sy=read(),ex=read(),ey=read();
if(sx==ex && sy==ey) puts("0"),exit(0);
ans=dij();
printf("%lld",ans==inf?-1:ans);
return 0;
}