CF590C Three States

CF590C Three States

题意翻译

给你一个?×?的地图，’.’为荒地，’#’为石头，数字为国家，求最少将多少个荒地修为路可以将三个国家联通。无解输出‘-1’。

---

题解：

0/1BFS

注意坑点是枚举到荒地的时候，要-2.

代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
struct node
{
	int x,y;
};
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
char ch[1010][1010];
int dis[1010][1010][5];
bool vis[1010][1010]; 
int n,m;
long long minn=0x3f3f3f3f3f3f3f3f;
void bfs(int s)
{
	deque<node> q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ch[i][j]-'0'==s)
			{
				dis[i][j][s]=0;
				q.push_back((node){i,j});
			}
	while(q.size())
	{
		node u=q.front();
		q.pop_front();
		int x=u.x;
		int y=u.y;
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx<1||xx>n||dis[x][y][s]+1>=dis[xx][yy][s]||yy<1||yy>m||ch[xx][yy]=='#')
				continue;
			if(ch[xx][yy]=='.')//标准01BFS
			{
				dis[xx][yy][s]=dis[x][y][s]+1;
				q.push_back((node){xx,yy});
			}
			else 
			{
				dis[xx][yy][s]=dis[x][y][s];
				q.push_front((node){xx,yy});
		    }
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>ch[i][j];
	memset(dis,INF,sizeof(dis));
	bfs(1);
	bfs(2);
	bfs(3);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			long long cost=1ll*dis[i][j][1]+dis[i][j][2]+dis[i][j][3];
			if(ch[i][j]=='.')
				cost-=2;	
			minn=min(minn,cost);
		}
	if(minn>=INF)
		cout<<"-1";
	else 
		cout<<minn;
	return 0;
}