题意:
一个n∗m迷宫,迷宫中每个格子用0或1表示,0表示该格子可以通过,1表示该格子是个障碍物,牛妹站在格子(1,1),出口在格子(n,m),牛妹想要走出迷宫,但牛妹只会按以下策略走:
牛妹当前所在的格子称为当前格子
如果当前格子右边没有障碍物,牛妹就向右走,否则转到2。
如果当前格子下方没有障碍物,牛妹就向下走,否则转到3。
如果当前格子左边没有障碍物,牛妹就向左走,否则转到4。
如果当前格子上方没有障碍物,牛妹就向上走,否则转到5。
牛妹站在原地不动。
由于牛妹按这样的策略可能会无法走到出口,牛妹的好朋友牛牛决定在牛妹离开格子{(1,1)}前把迷宫中的一些非障碍格子变成障碍,帮助牛妹走出迷宫,但是牛牛比较懒,他想要最小化变成障碍的非障碍格子的数量。
数据范围 
Strategy: 一开始在纸上模拟了一下, 确实发现会有左右走循环的情况, 往上走没意义也可以说是发现了, 但是没有想到, 他不能往左走或者往上走, 现在想来, 真的是莫名有点蠢. 这种题又不是第一次见了,,, . 总之推出只能往右下两个方向走以后就是基础dp了, 好在数据不很大, 其实数据要出大一点用滚动数组反而更好, 只是好多人都卡到第一步了(尤其是我)
dp部分: dp[i][j] = min(dp[i - 1][j] + (mat[i - 1][j + 1] == '0'), dp[i][j - 1])(从左边过来, 或者从上边过来的最少的代价)
特别注意, 初始化long long 数组的时候别用memset 0x3f3f3f3f, 因为并不会初始化成你想要的结果,反而是更大的一个值, 最好的解决方案就是不用memset, 可以用fill, 或者vector初始化(一晚上+出题人指点得出来的教训)., 如果有大佬知道适合memset使用的初始化longlong型数组的极大值, 我下跪恳求分享!!
迎评
#include <bits/stdc++.h> using namespace std; #define _rep(n, a, b) for (ll n = (a); n <= (b); ++n) #define _rev(n, a, b) for (ll n = (a); n >= (b); --n) #define _for(n, a, b) for (ll n = (a); n < (b); ++n) #define _rof(n, a, b) for (ll n = (a); n > (b); --n) #define oo 0x3f3f3f3f3f3f3f3fll #define ll long long #define db double #define eps 1e-8 #define bin(x) cout << bitset<10>(x) << endl; #define what_is(x) cerr << #x << " is " << x << endl #define met(a, b) memset(a, b, sizeof(a)) #define all(x) x.begin(), x.end() #define pii pair<ll, ll> #define pdd pair<db, db> const ll maxn = 1e3 + 100; const ll mod = 1e9 + 7; char mat[maxn][maxn]; ll dp[maxn][maxn]; signed main() { ll n, m; cin >> n >> m; met(dp, oo); _rep(i, 1, n) cin >> (mat[i] + 1); dp[1][1] = 0; _rep(i, 1, n) { _rep(j, 1, m) { if (i == 1 && j == 1)continue; if (mat[i][j] == '1')continue; dp[i][j] = min(dp[i - 1][j] + (ll)(mat[i - 1][j + 1] == '0'), dp[i][j - 1]); } } cout << (dp[n][m] >= oo ? -1 : dp[n][m]) << endl; }