abc 283 E Don't Isolate Elements

abc 283 E Don't Isolate Elements

题意:

给出一个 \(h * w\) 的01矩阵，对于每一行，可以进行翻转操作。

如果 \(a_{i,j}\) 的上下左右没有一个和它数值一样的话，这个点就被称为孤立点，求使得该矩阵没有孤立点需要的最少操作次数，如果不存在就输出 \(-1\)

思路:

每一行只有两种情况，翻转或者不翻转，很自然的就想到了动态规划。

我们摆放第 \(i\) 行的时候，需要判断第 \(i - 1\) 行是否合法，所以定义状态为 \(f[i][j][k]\) 为 前 \(i\) 行摆放完毕，第 \(i - 1\) 行的选择为 \(j\) ，第 \(i\) 行的选择为 \(k\) 时合法需要的最少操作次数。

然后，每次转移的时候，判断当前选择是否合法即可。

转移方程为: $ f[i][j][k] = min(f[i][j][k], f[i - 1][u][j] + k);$

实现:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5, INF = 1e9;
int h, w;
int a[N][N];
int f[N][2][2];
int check(int x, int a2, int a1, int a3)
{
    //第2行特判
    if (x <= 1)
    {
        if (x == 0)
            return 1;
        for (int i = 1; i <= w; i++)
        {
            int u = 0;
            if (a[x][i] ^ a2 == a[x + 1][i] ^ a1)
                u |= 1;
            if (i + 1 <= w && a[x][i] == a[x][i + 1])
                u |= 1;
            if (i - 1 >= 1 && a[x][i] == a[x][i - 1])
                u |= 1;
            if (!u)
                return 0;
        }
        return 1;
    }
    // 判断a2是否每个都有相连的
    for (int i = 1; i <= w; i++)
    {
        int u = 0;
        if (a[x][i] ^ a2 == a[x - 1][i] ^ a3 || a[x][i] ^ a2 == a[x + 1][i] ^ a1)
            u |= 1;
        if (i + 1 <= w && a[x][i] == a[x][i + 1])
            u |= 1;
        if (i - 1 >= 1 && a[x][i] == a[x][i - 1])
            u |= 1;
        if (!u)
            return 0;
    }

    //当摆放最后一行时，需要特判
    if (x + 1 == h)
    {
        x++;
        for (int i = 1; i <= w; i++)
        {
            int u = 0;
            if (a[x][i] ^ a1 == a[x - 1][i] ^ a2)
                u |= 1;
            if (i + 1 <= w && a[x][i] == a[x][i + 1])
                u |= 1;
            if (i - 1 >= 1 && a[x][i] == a[x][i - 1])
                u |= 1;
            if (!u)
                return 0;
        }
    }
    return 1;
}

int main()
{
    scanf("%d%d", &h, &w);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= h; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                f[i][j][k] = INF;

    // 前 i 行已经摆好
    for (int i = 1; i <= h; i++)
        // 第 i - 1 行的状态
        for (int j = 0; j < 2; j++)
            // 第 i 行的状态
            for (int k = 0; k < 2; k++)
                // 第 i - 2 行的状态
                for (int u = 0; u < 2; u++)
                {
                    if (check(i - 1, j, k, u))
                    {
                        f[i][j][k] = min(f[i][j][k], f[i - 1][u][j] + k);
                    }
                }

    int res = INF;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
        {
            res = min(res, f[h][i][j]);
        }
    if (res == INF)
        res = -1;
    printf("%d\n", res);
    return 0;
}