Codeforces Round #327 (Div. 1) C. Three States
5 seconds
512 megabytes
standard input
standard output
The famous global economic crisis is approaching rapidly, so the states of Berman, Berance and Bertaly formed an alliance and allowed the residents of all member states to freely pass through the territory of any of them. In addition, it was decided that a
road between the states should be built to guarantee so that one could any point of any country can be reached from any point of any other State.
Since roads are always expensive, the governments of the states of the newly formed alliance asked you to help them assess the costs. To do this, you have been issued a map that can be represented as a rectangle table consisting of n rows
and m columns. Any cell of the map either belongs to one of three states, or is an area where it is allowed to build a road, or is
an area where the construction of the road is not allowed. A cell is called passable, if it belongs to one of the states, or the road was built in this cell. From any passable cells you can move
up, down, right and left, if the cell that corresponds to the movement exists and is passable.
Your task is to construct a road inside a minimum number of cells, so that it would be possible to get from any cell of any state to any cell of any other state using only passable cells.
It is guaranteed that initially it is possible to reach any cell of any state from any cell of this state, moving only along its cells. It is also guaranteed that for any state there is at least one cell that belongs to it.
The first line of the input contains the dimensions of the map n and m (1 ≤ n, m ≤ 1000) —
the number of rows and columns respectively.
Each of the next n lines contain m characters,
describing the rows of the map. Digits from 1 to 3 represent
the accessory to the corresponding state. The character '.' corresponds to the cell where it is allowed to build a road and the character '#'
means no construction is allowed in this cell.
Print a single integer — the minimum number of cells you need to build a road inside in order to connect all the cells of all states. If such a goal is unachievable, print -1.
4 5
11..2
#..22
#.323
.#333
2
1 5
1#2#3
-1
题意：有三个国家，要建造一些桥，使得三个国家能相互连通，问最少要造多少桥。
思路：共有两种情况，一种是先使得两个国家连通，然后再使它们和另一个连通，还有一种是设一个点，造桥使得这三个国家都到这个点。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 99999999
#define maxn 1005
char s[maxn][maxn];
int dist[maxn][maxn][4],vis[maxn][maxn]; //dsit[i][j][num]表示坐标为i,j的点到值为num所对的这个国家的最小要造的桥数
int st[4][2],n,m;
int ans[4][4]; //ans[i][j]表示i国家和j国家要连通所要造的桥的个数
int tab[4][2]={0,1,-1,0,0,-1,1,0};
int q[1111111][3];//0 x,1 y,2 t
void bfs(int num)
{
int i,j,x,y,t,xx,yy,tt;
int front,rear;
front=rear=1;
x=st[num][0];
y=st[num][1];
q[front][0]=x;
q[front][1]=y;
q[front][2]=0;
dist[x][y][num]=0;
vis[x][y]=1;
while(front<=rear){ //这里先把值为num的国家都找出来，这些都是连通的
x=q[front][0];
y=q[front][1];
t=q[front][2];
front++;
for(i=0;i<4;i++){
xx=x+tab[i][0];
yy=y+tab[i][1];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && s[xx][yy]-'0'==num && !vis[xx][yy]){
vis[xx][yy]=1;
dist[xx][yy][num]=0;
rear++;
q[rear][0]=xx;
q[rear][1]=yy;
q[rear][2]=0;
}
}
}
front=1; //这里值为num的国家要再次放入队列
while(front<=rear){
x=q[front][0];
y=q[front][1];
t=q[front][2];
front++;
for(i=0;i<4;i++){
xx=x+tab[i][0];
yy=y+tab[i][1];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && s[xx][yy]!='#' && !vis[xx][yy]){
vis[xx][yy]=1;
if(s[xx][yy]=='.'){
dist[xx][yy][num]=t+1;
rear++;
q[rear][0]=xx;
q[rear][1]=yy;
q[rear][2]=t+1;
}
else{
int cot=s[xx][yy]-'0';
dist[xx][yy][num]=t+1;
ans[num][cot]=min(ans[num][cot],t+1);
rear++;
q[rear][0]=xx;
q[rear][1]=yy;
q[rear][2]=t+1;
}
}
}
}
}
int main()
{
int i,j,ant;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(j=1;j<=m;j++){
if(s[i][j]=='1'){
st[1][0]=i;st[1][1]=j;
}
if(s[i][j]=='2'){
st[2][0]=i;st[2][1]=j;
}
if(s[i][j]=='3'){
st[3][0]=i;st[3][1]=j;
}
dist[i][j][1]=dist[i][j][2]=dist[i][j][3]=inf;
}
}
for(i=1;i<=3;i++){
for(j=1;j<=3;j++){
if(i!=j){
ans[i][j]=inf;
}
else ans[i][j]=0;
}
}
for(i=1;i<=3;i++){
memset(vis,0,sizeof(vis));
bfs(i);
}
ant=inf;
ant=min(ant,ans[1][2]+ans[1][3]-2);
ant=min(ant,ans[2][1]+ans[2][3]-2);
ant=min(ant,ans[3][1]+ans[3][2]-2);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(s[i][j]!='#'){
if(s[i][j]=='.'){
ant=min(ant,dist[i][j][1]+dist[i][j][2]+dist[i][j][3]-2);
}
else{
ant=min(ant,dist[i][j][1]+dist[i][j][2]+dist[i][j][3]-2);
}
}
}
}
if(ant>10000000)printf("-1\n");
else printf("%d\n",ant);
}
return 0;
}
最新文章
- MVC4做网站后台:用户管理 ——用户组
- Surprise团队第二周项目总结
- Devrama Slider - 支持任意 HTML 的内容滑块
- SSH+Ext+mysql快速开发
- [转]Flash Socket通信的安全策略
- linux系统制作简单流程
- .htaccess 使用大全
- idea配github
- 浅析Javascript单例模式
- 微信小程序支付接入注意点
- SonarQube 中文教程 （1）- 简介
- Leetcode 344.反转字符串 By Python
- java内部类（三）
- 如何在gvim中安装autoproto自动显示函数原型
- Linux下查/删/替 命令(转)
- 搭建项目Maven+springMVC+hibernate时，JUnit測试出现报ClassNotFoundException错误的解决
- Metasploit小技巧
- SpringMVC 原理和流程
- 跨域资源共享/option 请求产生原因
- Angular: 使用 RxJS Observables 来实现简易版的无限滚动加载指令