[ABC351D] Grid and Magnet 题解

· · 题解

有一张 n \times m 的网格图，某些位置上可能会有磁铁。

如果与你当前位置周围有磁铁（四联通），你就不能移动。

定义一个没有磁铁的位置的自由度为从这里出发，能到达的最大点数，求网格图上的最大自由度。

显然，我们可以 DFS 搜索，如果当前这个点不是磁铁，并且这个点以前没有搜过，那我们就从它开始搜索。

如果搜到周围有磁铁就直接退出，因为我们不能再走了。

否则我们就看周围的点是否在这次搜索中搜过，如果没有我们就往那里搜。

要注意的是，是这次搜索，以前从别的点开始搜索的不算，怎么办呢。

一个点最近一次是第 x 次搜到的，我们就可以把这个点的标记数组设为 x，

判断时看它的标记数组是否为这次搜索就可以了。

code

跑了 66ms，速度比 BFS 快一些。

int n,m,ans,cnt,s,f[N][N];
char a[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},tx,ty;
void dfs(int x,int y,int s){
    cnt++,ans=max(ans,cnt),f[x][y]=s;
    rep(i,0,3){
        tx=x+dx[i],ty=y+dy[i];
        if(a[tx][ty]=='#') return;
    }
    rep(i,0,3){
        tx=x+dx[i],ty=y+dy[i];
        if(tx>0&&ty>0&&tx<=n&&ty<=m&&f[tx][ty]!=s) dfs(tx,ty,s);
    }
}
signed main(){
    read(n,m);
    rep(i,1,n)rep(j,1,m)read(a[i][j]);
    rep(i,1,n)rep(j,1,m) if(a[i][j]=='.'&&!f[i][j]){cnt=0;dfs(i,j,++s);}
    cout<<ans;
    return 0;
}