Topcoder SRM 637 Div2 T3 ConnectingGameDiv2 题解

This blog post is only available in Simplified Chinse.

Topcoder SIngle Round Match 637 Div 2 T3 ConnectingGameDiv2 题解

Translation

给你一个 N×M 的字符矩阵，每个字符可能是大写字母、小写字母或者数字。相同字符的一块联通块称为一个“区域”。现在要选取这个矩阵里的几个区域染成红色，使得从矩阵的第一行到最后一行没有一条没有颜色的通路。换句话说，染成红色的点就不能走了，要使得第一行到最后一行没有通路。你的任务是使得染色的 cells 个数最少。注意：只能一次染一个区域。字符矩阵以 vector board 给出。数据范围： $1 \leqslant n,m \leqslant 50$ 。

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

染两个 A 或者 B 和 C 均可。

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

方案之一是染 B 和 C，一共 4 个 cells。

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

唯一的方案是把一圈 i 都染了。

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

据说这题可以用最大流做，是最大流最小割问题，但是我和 DYT 研究讨论了一晚上没想到好的解决方案……不过我们想到一种更加简单的想法……

既然题目里要我们“使得第一行到最后一行没有通路”，自然就可以想到我们可以去“阻断”从上到下的路。问题可以变成：要从最左边一列到最右边一列画一条弯曲的线，即只要染了这条“线”上的 cells 就可以“阻断通路”。其所经之处的区域的所有 cells 都要被染色，即加上区域所含 cells 的个数。我们要找到所经区域 cells 个数之和最小的一条“线”。很明显就是一个变形的最短路。可以用 SPFA（Bellman-Ford）算法解决。需要注意要考虑八个方向（即八联通），形如这样的围法（斜连接）也可以阻断道路：

OOX \\ XXO \\ OOO

关于最小割最大流（min-cut max flow）的解法，我们看了一位外国大佬的解法，和几篇日本选手的题解（第一篇和第二篇），但是都没看懂…… （Google 翻译日语翻译过来根本看不懂啊……）

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()){
		WT head=que.front();que.pop();
		vis[head.x][head.y]=false;
		for (int i=0;i<8;i++) if (CheckMove(head.x+move_eight[i][0],head.y+move_eight[i][1])){
			int xx=head.x+move_eight[i][0],yy=head.y+move_eight[i][1];
			if (dst[head.x][head.y]+sum[num[xx][yy]]*(bool)(num[xx][yy]!=num[head.x][head.y])<dst[xx][yy]){
				dst[xx][yy]=dst[head.x][head.y]+sum[num[xx][yy]]*(bool)(num[xx][yy]!=num[head.x][head.y]);
				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;
}

8/29/2018