# Topcoder SRM 637 Div2 T3 ConnectingGameDiv2 题解

2018 年 8 月 29 日 12:45

## 文章目录

Topcoder SIngle Round Match 637 Div 2 T3 ConnectingGameDiv2 题解

## Translation

• board will contain between 1 and 50 elements, inclusive.
• Each element in board will contain between 1 and 50 characters, inclusive.
• All elements in board will have the same length.
• Each character in board will be a letter or a digit (’a'-'z', 'A'-'Z', or '0'-'9').
• Each of the regions in board will be 4-connected.
• Time limit (s): 2.000
• Memory limit (MB): 256

## Examples

{"AA"
,"BC"}


Returns: 2

If Snuke colors 0 or 1 cells red, he will lose the game. He can win the game by coloring 2 cells red. One possibility is to color the two 'A' cells red.

{"AAB"
,"ACD"
,"CCD"}


Returns: 4

Here, one optimal solution is to color the regions 'B' and 'C' red. There will be 1 + 3 = 4 red cells.

{"iii"
,"iwi"
,"iii"}


Returns: 8

## Original

Cat Snuke and wolf Sothe are playing the Connecting Game.
The Connecting Game is played on a rectangular grid that is divided into unit square cells. The grid is divided into some regions. Each cell belongs into exactly one of those regions. Each region is 4-connected (see Notes for a formal definition).
You are given a vector board that describes the division of the grid into regions. Each character in board represents one of the cells. Cells that are represented by the same character belong into the same region.
Initially, the entire grid is colorless. The game consists of two steps. In the first step, Snuke colors some of the regions red. In the second step, Sothe colors all remaining regions blue. (Within each region, all cells must have the same color.) Sothe wins if there is a path (see Notes for a formal definition) of blue cells from the top row to the bottom row. Otherwise, Snuke wins.
You are given the vector board. Compute and return the smallest number of cells Snuke can color red in order to win the game.
(Note that Snuke cannot simply color individual cells, he must color entire regions. Also note that we are interested in minimizing the total number of cells, not the number of regions Snuke colors.)

## Analysis

OOX \\
XXO \\
OOO


## Code

TC 的编译器似乎 move 变量不能开……

#include <bits/stdc++.h>
#define CLEAR(x) memset(x,0,sizeof(x))
#define CLEAR_NEG(x) memset(x,255,sizeof(x))
#define CLEAR_MAX(x) memset(x,0x3f,sizeof(x))
#define CLEAR_MIN(x) memset(x,0x80,sizeof(x))
using namespace std;

const int maxn=2510,maxnn=55,INF=5e8;
const int mve[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
const int move_eight[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int n,nn,mm,ans=0;
int num[maxnn][maxnn],sum[maxn],dst[maxnn][maxnn];
bool vis[maxnn][maxnn];
vector <string> a;
struct WT{
int x,y;
};
queue <WT> que;

class ConnectingGameDiv2 {
public:
int getmin( vector <string> board );
};
inline void init(){
CLEAR(sum);CLEAR(vis);
CLEAR_NEG(num);
n=0;ans=INF;
}
inline bool CheckMove(int x,int y){
if (x<0||y<0||x>nn-1||y>mm-1) return false;
return true;
}
inline void MakeRegion(int x,int y,int id){
num[x][y]=id;sum[id]++;
for (int i=0;i<4;i++)
if (CheckMove(x+mve[i][0],y+mve[i][1])&&(num[x+mve[i][0]][y+mve[i][1]]==-1)&&(a[x+mve[i][0]][y+mve[i][1]]==a[x][y]))
MakeRegion(x+mve[i][0],y+mve[i][1],id);
}
inline void BuildSum(){
for (int i=0;i<nn;i++)
for (int j=0;j<mm;j++)
if (num[i][j]==-1) MakeRegion(i,j,++n);
// for (int i=0;i<nn;i++){
//  for (int j=0;j<mm;j++) printf("%d ",num[i][j]);
//  printf("\n");
// }
// printf("sum:");for (int i=1;i<=n;i++) printf("%d ",sum[i]);printf("\n");
}
inline int SPFA(int sx,int sy){
CLEAR_MAX(dst);
vis[sx][sy]=true;dst[sx][sy]=sum[num[sx][sy]];
que.push((WT){sx,sy});
while (!que.empty()){
if (!vis[xx][yy]) vis[xx][yy]=true,que.push((WT){xx,yy});
}
}
}
int ret=INF;
for (int i=0;i<nn;i++) ret=min(ret,dst[i][mm-1]);
return ret;
}
int ConnectingGameDiv2::getmin(vector <string> board) {
init();
nn=board.size();mm=board[0].length();
a=board;
BuildSum();
for (int i=0;i<nn;i++) ans=min(ans,SPFA(i,0));
return ans;
}