ZOJ 3781 Paint the Grid Reloaded（BFS+缩点思想）

Paint the Grid Reloaded

Time Limit: 2 Seconds Memory Limit: 65536 KB

Leo has a grid with N rows and M columns. All cells are painted with either black or white initially.

Two cells A and B are called connected if they share an edge and they are in the same color, or there exists a cell C connected to both A and B.

Leo wants to paint the grid with the same color. He can make it done in multiple steps. At each step Leo can choose a cell and flip the color (from black to white or from white to black) of all cells connected to it. Leo wants to know the minimum number of steps he needs to make all cells in the same color.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N and M (1 <= N, M <= 40). Then N lines follow. Each line contains a string with N characters. Each character is either 'X' (black) or 'O' (white) indicates the initial color of the cells.

Output

For each test case, output the minimum steps needed to make all cells in the same color.

Sample Input

2

2 2

OX

OX

3 3

XOX

OXO

XOX

Sample Output

1

2

Hint

For the second sample, one optimal solution is:

Step 1. flip (2, 2)

XOX

OOO

XOX

Step 2. flip (1, 2)

XXX

XXX

XXX

题目链接：ZOJ 3781

前段时间受同学邀请去打了一个小小的比赛，内容是11届浙江省赛题目（除去了某道现场AC率最低的那题），由于还是图样，最后仅五题滚粗，这种比赛对于我这种学过那么一点点算法的人但又不精通的人来说就是不会写，跟没学过算法的人来说没啥区别，果然还是太菜鸟了，这题比赛的时候只想到是BFS，然后硬是写了一个用map的暴力，结果内存爆了（意料之中），后来想想以为是字符只有两种，可能用某种压缩储存的办法，然而看了题解发现是普通的BFS，只是用到了缩点的思想（反正我想不出来，这办法真的很巧妙）。

可以这样想：题目显然是同样的颜色邻近的点是同一个连通分量中的，翻动任意一个会使得这整个连通分量都发生变化，那么这整个分量中的点均为等价的，然后枚举一开始翻的分量i，若在第一次翻i的条件下想全部翻为同色，则至少要找到那个离i最远的分量j，两者之间隔的距离就是至少翻过的次数，这样一来枚举每一个点进行BFS然后取其中dis[i][j]的最大值更新ans的最小值就好了。当然事先得暴力地把点缩一下

代码：

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 45;

struct edge

{

    int to, nxt;

    edge() {}

    edge(int _to, int _nxt): to(_to), nxt(_nxt) {}

};

edge E[(N * N * 4) << 1];

int head[N * N], tot;

int d[N * N];

bitset<N*N>vis;

bool link[N * N][N * N];

char pos[N][N];

int id[N][N], dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};

int n, m;

void init()

{

    CLR(head, -1);

    tot = 0;

    CLR(id, 0);

    CLR(link, false);

}

inline void add(int s, int t)

{

    E[tot] = edge(t, head[s]);

    head[s] = tot++;

}

void bfs(int s)

{

    CLR(d, INF);

    vis.reset();

    queue<int>Q;

    Q.push(s);

    d[s] = 0;

    vis[s] = 1;

    while (!Q.empty())

    {

        int u = Q.front();

        Q.pop();

        for (int i = head[u]; ~i; i = E[i].nxt)

        {

            int v = E[i].to;

            if (!vis[v])

            {

                vis[v] = 1;

                d[v] = d[u] + 1;

                Q.push(v);

            }

        }

    }

}

inline bool check(int x, int y)

{

    return x >= 0 && x < n && y >= 0 && y < m;

}

void dfs(int x, int y, int ID)

{

    id[x][y] = ID;

    for (int i = 0; i < 4; ++i)

    {

        int vx = x + dir[i][0];

        int vy = y + dir[i][1];

        if (check(vx, vy) && pos[vx][vy] == pos[x][y] && !id[vx][vy])

            dfs(vx, vy, ID);

    }

}

int main(void)

{

    int tcase, i, j;

    scanf("%d", &tcase);

    while (tcase--)

    {

        init();

        scanf("%d%d", &n, &m);

        for (i = 0; i < n; ++i)

            scanf("%s", pos[i]);

        int cntid = 0;

        for (i = 0; i < n; ++i)

            for (j = 0; j < m; ++j)

                if (!id[i][j])

                    dfs(i, j, ++cntid);

        for (i = 0; i < n; ++i)

        {

            for (j = 0; j < m; ++j)

            {

                for (int k = 0; k < 4; ++k)

                {

                    int ii = i + dir[k][0];

                    int jj = j + dir[k][1];

                    if (check(ii, jj) && pos[ii][jj] != pos[i][j] && !link[id[i][j]][id[ii][jj]] && !link[id[ii][jj]][id[i][j]])//link数组防止无用的重边

                    {

                        add(id[i][j], id[ii][jj]);

                        add(id[ii][jj], id[i][j]);

                        link[id[i][j]][id[ii][jj]] = link[id[ii][jj]][id[i][j]] = true;

                    }

                }

            }

        }

        int ans = n * m;

        for (i = 1; i <= cntid; ++i)

        {

            bfs(i);

            ans = min(ans, *max_element(d + 1, d + cntid + 1));

        }

        //cout<<tot<<endl;

        printf("%d\n", ans);

    }

    return 0;

}

巴特西