WUOJ#15 奇妙的棋盘

题目描述

因为前面选手们的帮忙，小蛤智商提升了！他现在在玩一个神奇的游戏:给出了一个n×m的棋盘，其中的格子有的黑，有的白。我们对一个格子进行操作，可以使这个格子与它所处的颜色相同的联通块中的所有格子颜色全部取反。问至少要多少次操作可以使所有格子变白？

输入格式

第一行两个整数n，m代表棋盘尺寸；接下n行一个字符串描述每一行棋盘情况：W为白B为黑

输出格式

输出一个整数表示最少的次数。

样例数据

样例下载

数据规模与约定

对于40%的数据 $n \times m \leq 20$

对于70%的数据 $n \leq 20, m \leq 20$

对于100%的数据 $n \leq 70, m \leq 70$

时间限制： $1 s$

空间限制： $256 MB$

首先预处理所有连通块，缩成一个个点，连边权为1的无向边，然后对于每一个点跑单源最短路求距离最大的点。但是注意到最短路算法肯定会TLE，又因为边长为1，可以想到用BFS n^2 求解，至此，O(n ^ 2 * m ^ 2)。代码：

#include<cstdio> #include<queue> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n, m; const int maxn = 75; bool vis[maxn][maxn]; bool rev[maxn * maxn], type[maxn * maxn]; int idx[maxn][maxn], cnt, ans; char map[maxn][maxn]; bool coned[maxn * maxn][maxn * maxn]; vector<int > con[maxn * maxn]; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; bool illegal(int x, int y, int ox, int oy, char type) { if(x < 0 || y < 0 || x >= n || y >= m) return true; if(map[x][y] != type) { if(vis[x][y]) { if(!coned[idx[ox][oy]][idx[x][y]]) con[idx[ox][oy]].push_back(idx[x][y]), coned[idx[ox][oy]][idx[x][y]] = 1; if(!coned[idx[x][y]][idx[ox][oy]]) con[idx[x][y]].push_back(idx[ox][oy]), coned[idx[x][y]][idx[ox][oy]] = 1; } return true; } if(vis[x][y]) return true; return false; } void dfs(int x, int y, int id, char type) { vis[x][y] = 1; idx[x][y] = id; int nx, ny; for(register int i = 0; i < 4; ++i) { nx = x + dx[i]; ny = y + dy[i]; if(illegal(nx, ny, x, y, type)) continue; dfs(nx, ny, id, type); } } void pre() { for(register int i = 0; i < n; ++i) for(register int j = 0; j < m; ++j) if(!vis[i][j]) dfs(i, j, cnt++, map[i][j]), type[cnt - 1] = map[i][j] == 'W'; } struct node {int num, step;node(int a, int b){num = a, step = b;}}; int bfs() { int ans = 0, mn = 0x3f3f3f3f; for(register int i = 0; i < cnt; ++i) { memset(rev, 0, sizeof(rev)), ans = 0; queue<node > q; q.push(node(i, 0)), rev[i] = 1; while(!q.empty()) { int now = q.front().num; int step = q.front().step; q.pop(); ans = max(ans, step); for(register int j = con[now].size() - 1; j >= 0; --j) { int v = con[now][j]; if(rev[v]) continue; rev[v] = 1; q.push(node(v, step + 1)); } } if(type[i] == 1) ans += ans % 2; if(type[i] == 0) ans += ans % 2 == 0; mn = min(ans, mn); } return mn; } int main() { scanf("%d%d", &n, &m); for(register int i = 0; i < n; ++i) scanf("%s", map[i]); pre(); printf("%d", bfs()); return 0; }

Rockdu's Blog