思维、暴力枚举、遍历
题意:
给一个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; }
个人感觉,难度主要在于能不能走出动态规划的坑,思维上有难度。
另外,对于二维矩阵的对角线扫描我认为也是有一定的难度的。。。