题解 - 矩阵

题目描述

小明和小花知道学信息学竞赛的学生特别擅长做一些和矩阵相关的问题。例如，同学经常做的一个题目，给你一个 N × M 的矩阵，矩阵里面每个格子上都有一个数，要从左上角 (1,1)，走到右下角 (N,M)，每一步只能往下或者往右走，让你求经过的路径上数的总和最小。小明和小花发现这个问题太简单了，根本难不倒广大的 OIer。
于是，他们开始别出心裁了。
他们想着现在给你一个 01 矩阵（即里面每个格子上的数是 0 或者 1），仍旧让你从 (1,1) 走到 (N,M)，每次只能往下面一个格子或者右边一个格子走。定义一条好路径是从起点到终点只经过 0 的格子。但是现在由于 1 的格子太多，所以可能无法完成这个任务。
于是，他们想出了修改操作，对于每个修改操作 (x1,y1)(x2,y2)，表示把以 (x1,y1) 为左上角，以 (x2,y2) 为右下角的子矩阵里面每个格子里面的数进行反转，即 0 变成
1，1 变成 0。
问题是：最少需要多少次操作，才能使得这个矩阵存在好路径。现在请你来计算。

输入

输入的第一行是一个正整数 T，表示矩阵的个数。
对于每个矩阵：
输入第一行是 2 个正整数 N 和 M，表示矩阵的行数和列数。
接下来输入 N 行，每行有 M 个数，都是 0 或者 1，空格隔开。

输出

输出 T 个非负整数，每行一个数，表示最少需要的操作数，使得对应矩阵存在好路径。

样例

样例输入

【输入样例1】
1
3 3
0 1 1
0 1 0
1 1 0
【输入样例2】
1
5 5
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
【输入样例3】
2
10 10
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 1 1
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1

样例输出

【输出样例1】
1
【输出样例2】
4
【输出样例3】
1
1

提示

分析

将最终路径看作01串，则翻转操作只会影响连续的一段数，

即转化为给定01串，问最少区间反转多少次，使得01串全变成0，线性dp即可

一维：

若a[i] == 0，则 f[i] = f[i - 1]

若a[i] != 0，则 f[i] = f[i - 1] + (a[i - 1]==0)

二维：

若a[i][j] == 0，则 f[i][j] = min(f[i][j - 1] + (a[i][j - 1] == 0),f[i - 1][j] + (a[i - 1][j] == 0))

若a[i][j] != 0，则 f[i][j] = min(f[i][j - 1],f[i - 1][j])

代码

#pragma GCC optimize(2)
  
#include<bits/stdc++.h>
   
using namespace std;
   
typedef long long LL;
   
const int N = 1e3 + 10,M = 1e6 + 10;
 
int n,m;
int a[N][N];
int f[N][N];
 
void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            cin >> a[i][j];
 
    f[1][1] = a[1][1];
    for(int i = 2;i <= m;i++){
        if(a[1][i]) f[1][i] = f[1][i - 1] + (a[1][i - 1] == 0);
        else f[1][i] = f[1][i - 1];
    } 
    for(int i = 2;i <= n;i++){
        if(a[i][1]) f[i][1] = f[i - 1][1] + (a[i - 1][1] == 0);
        else f[i][1] = f[i - 1][1];
    }
 
    for(int i = 2;i <= n;i++)
        for(int j = 2;j <= m;j++){
            if(a[i][j]) f[i][j] = min(f[i][j - 1] + (a[i][j - 1] == 0),f[i - 1][j] + (a[i - 1][j] == 0));
            else f[i][j] = min(f[i][j - 1],f[i - 1][j]);
        }
 
    cout << f[n][m] << '\n';    
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        solve();
    }
 
    return 0;
}