题目大意
更改尽量少的格子使得三个连通块连通。
思路
其他 dalao 都是分两种情况讨论：
情况一 情况二
11....33 11*+**33
11*22*33 ...*....
...22... ...22...
两两相连 连于一点
我也是这么想的，但是我不想分情况，怎么办？
合并成一种！
11....33 11....33
11*22*33 -> 11*+**33
...22... ...22...
两两相连就相当于连于某一个连通块内部一点，只不过连通块里面的不计代价。
怎么找这个点呢？
我们不去枚举这个点，这样太慢了。
我们让每一个连通块出来拓展，直到一个点被三个连通块都拓展过，然后更新答案。
先 BFS 求连通块。
把所有 X 点按连通块推进队列，用 Visit 数组记录点到三个连通块的代总和， ViFrom ( 数组二进制压缩记录点被哪些连通块遍历过。Visit From)
因为在连通块里面拓展是不计代价的，破坏了 queue BFS 的单调性（代价小的先拓展），所以我们用 priority_queue 强制维护单调性。
实现
找联通块
注意在推点的时候把这个点的 ViFrom 标记一下。
bool OutMap(int x,int y){return x<0||x>=N||y<0||y>=M;}
void Fill(int Sx,int Sy,int Odd)
{
Map[Sx][Sy]=Odd;
Filler.push({Sx,Sy});
Search.push({Sx,Sy,Odd,0});
ViFrom[Sx][Sy]^=1<<Odd;
while(!Filler.empty())
{
const Coord F=Filler.front();
Filler.pop();
for(int i=0;i<4;i++)
{
Nx=F.x+D[i][0],Ny=F.y+D[i][1];
if(OutMap(Nx,Ny)) continue;
if(Map[Nx][Ny]!=-1) continue;
Map[Nx][Ny]=Odd;
ViFrom[Nx][Ny]^=1<<Odd;
Search.push({Nx,Ny,Odd,0});
Filler.push({Nx,Ny});
}
}
return;
}
从三个连通块拓展
注意交于外面一点要减去2，因为相交的那一点（ ViFrom 等于 \((1110)_2\) ）会算三次。
void Find()
{
while(!Search.empty())
{
const Point F=Search.top();
Search.pop();
for(int i=0;i<4;i++)
{
Nx=F.x+D[i][0],Ny=F.y+D[i][1],NLv=F.Lv;
if(OutMap(Nx,Ny)) continue;
if((ViFrom[Nx][Ny]>>F.From)&1) continue;
if(Map[Nx][Ny]==0) NLv++;
ViFrom[Nx][Ny]^=1<<F.From,Visit[Nx][Ny]+=NLv;
if(ViFrom[Nx][Ny]==14)
{
if(Map[Nx][Ny]==0) Visit[Nx][Ny]-=2;
Fans=min(Fans,Visit[Nx][Ny]);
}
Search.push({Nx,Ny,F.From,NLv});
}
}
return;
}
完整代码
#include<cstdio>
#include<queue>
using std::queue;
using std::priority_queue;
int min(int a,int b){return a<b?a:b;}
const int D[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int N,M,Fans=0x3fffffff,Nx,Ny,NLv,G=1;
int Map[55][55],Visit[55][55],ViFrom[55][55];
char In[55];
struct Coord{int x,y;};
struct Point
{
int x,y,From,Lv;
bool operator< (Point m)const{return Lv>m.Lv;}
};
queue<Coord> Filler;
priority_queue<Point> Search;
bool OutMap(int x,int y){return x<0||x>=N||y<0||y>=M;}
void Fill(int Sx,int Sy,int Odd)
{
Map[Sx][Sy]=Odd;
Filler.push({Sx,Sy});
Search.push({Sx,Sy,Odd,0});
ViFrom[Sx][Sy]^=1<<Odd;
while(!Filler.empty())
{
const Coord F=Filler.front();
Filler.pop();
for(int i=0;i<4;i++)
{
Nx=F.x+D[i][0],Ny=F.y+D[i][1];
if(OutMap(Nx,Ny)) continue;
if(Map[Nx][Ny]!=-1) continue;
Map[Nx][Ny]=Odd;
ViFrom[Nx][Ny]^=1<<Odd;
Search.push({Nx,Ny,Odd,0});
Filler.push({Nx,Ny});
}
}
return;
}
void Find()
{
while(!Search.empty())
{
const Point F=Search.top();
Search.pop();
for(int i=0;i<4;i++)
{
Nx=F.x+D[i][0],Ny=F.y+D[i][1],NLv=F.Lv;
if(OutMap(Nx,Ny)) continue;
if((ViFrom[Nx][Ny]>>F.From)&1) continue;
if(Map[Nx][Ny]==0) NLv++;
ViFrom[Nx][Ny]^=1<<F.From,Visit[Nx][Ny]+=NLv;
if(ViFrom[Nx][Ny]==14)
{
if(Map[Nx][Ny]==0) Visit[Nx][Ny]-=2;
Fans=min(Fans,Visit[Nx][Ny]);
}
Search.push({Nx,Ny,F.From,NLv});
}
}
return;
}
int main()
{
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++)
{
scanf("%s",In);
for(int j=0;j<M;j++)
Map[i][j]=(In[j]=='X')?-1:0;
}
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(Map[i][j]==-1)
Fill(i,j,G++);
Find();
printf("%d",Fans);
return 0;
}
81行，还算行吧