思维、暴力枚举、遍历

题意:

给一个nm的网格，小明起初在左上角，每次可以向右或向下走一格，'#'代表不能走的格子，'.'代表能走的格子，问至少要把原先的几个'.'改成'#',可以使小明不能到达右下角(左上角和右下角起初都为'.',并且不能被改成'#')
Input
输入的第一行是两个整数n,m(3≤n⋅m≤1000000 )。 接下来n行是一个nm的矩阵； 具体含义见描述。
Output
输出改变的最小数目，使得whgg不能到达右下角。

分析：

首先我们可以非常明显的推断出最终答案再集合{0,1,2}内。
因为，对于任何一个二维数组(n行m列)，记为a：
下面数组中1代表'.'可走，2代表'#'不可走
[1,1,1,1,1]
[1,1,2,1,2]
[2,2,2,2,2]
[1,2,2,2,1]
我们只需保证将a[n-1][m]和a[n-1][m]无法到达就可以了！！
那么最多不过我们将她们都变为零，消耗两次。

这很容易让人想到动态规划，但动态规划并不是本题的解法！！！！
我们先说一下动态规划吧。
我们可以总结出一个这样的公式：
dp[i][j] 表示阻止到达a[i][j]所需的最少消耗量。
if (a[i][j]==2)dp[i][j]=0;
dp[i][j] = dp[i-1][j]+dp[i][j-1]
我们很容易这样想，但事实上这是错的。
因为当我们加上dp[i-1][j]与dp[i][j-1]时，我们有可能加重复了，又或者根本不能这样做！！！
及，可能有格子，将其变为2既可以帮助不到达a[i-1][j]也可以帮助不到达a[i][j-1]
这是这题不能这样使用动态规划的原因。
我刚开始顺着动态规划的思维想了好久，惭愧！

下面给出正确思维：

我们想一想，对于矩阵：
[1,1,1,1,1]4
[1,1,2,1,2]3
[2,2,2,2,2]2
[1,2,2,2,1]1
5 4 3 2 1

外围的数字表示对角线，应该理解我的意思吧。

那看看我们的问题，其实就是不可以到达对角线1
那么怎么可以不到达对角线1呢？答案是不到达对角线2
那么怎么不到达对角线2呢？答案是不到达对角线3
。。。。。。。
更准确地说
使不到达对角线k，应该使对角线k+1中能够到达对角线k的格子变为2
使对角线k+!中能够到达对角线k的格子变为2是什么意思呢？
比如对于a[i][j]可以到达，但是a[i+1][j]不可以到达,且a[i][j+1]也不可以到达
那么我们就没有必要为其消耗，直接将其设为不可到达就好了。

而如何判断一个格点是否可以到达则需要动态规划了。
dp[i][j]为a[i][j]是否可以到达
if a[i][j] == 2:dp[i][j]=false
else dp[i][j] = dp[i-1][j]||dp[i][j-1]

如此我们遍历每一条对角线记录这条对角线消耗的次数，在其中取最小就行了
注意第一条和最后一条不遍历

代码如下，注意细节

#include<iostream>;
#include<vector>;
#include<algorithm>;
using namespace std;
typedef pair<int, int> pii;
vector<vector<bool>> dp;
int n, m;

bool help(int i, int j) {
    if (i == n - 1 && j == m - 1)return false;
    if (i == n - 1)return dp[i][j + 1];
    if (j == m - 1)return dp[i + 1][j];
    return dp[i + 1][j] || dp[i][j + 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    dp.resize(n);
    for (int i = 0;i < n;i++)dp[i].resize(m);
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            char ch;cin >> ch;
            if (ch == '.')dp[i][j] = true;
            else dp[i][j] == false;
        }
    }
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (!dp[i][j])dp[i][j] = false;
            else if (i == 0 && j == 0)dp[i][j] = dp[i][j];
            else if (i == 0)dp[i][j] = dp[i][j - 1];
            else if (j == 0)dp[i][j] = dp[i - 1][j];
            else dp[i][j] = (dp[i - 1][j] || dp[i][j - 1]);
        }
    }
    int ans = 3;int len = m + n - 3;
    for (int i = n - 2;i >= 0;i--) {
        int cnt = 0;int tmp = i;
        for (int j = m - 1;j >= 0 && tmp < n;j--) {
            if (dp[tmp][j] && help(tmp, j))cnt++;
            if (!help(tmp, j))dp[tmp][j] = false;
            tmp++;
        }
        ans = min(ans, cnt);
        len--;
        if (!len) {
            break;
        }
    }
    if (len > 0) {
        for (int j = m - 2;j > 0;j--) {
            int cnt = 0;int tmp = j;
            for (int i = 0;i < n && tmp >= 0;i++) {
                if (dp[i][tmp] && help(i, tmp))cnt++;
                if (!help(i, tmp))dp[i][tmp] = false;
                tmp--;
            }
            ans = min(ans, cnt);
            len--;
            if (!len)break;
        }
    }
    cout << ans << endl;
}

个人感觉，难度主要在于能不能走出动态规划的坑，思维上有难度。
另外，对于二维矩阵的对角线扫描我认为也是有一定的难度的。。。