cf1072D. Minimum path(BFS)

题意

题目链接

给出一个\(n \times n\)的矩阵，允许修改\(k\)次，求一条从\((1, 1)\)到\((n, n)\)的路径。要求字典序最小

sol

很显然的一个思路是对于每个点，预处理出从\((1, 1)\)到该点最多能经过多少个\(1\)

然后到这里我就不会做了。。

接下来应该还是比较套路的吧，就是类似于bfs一样，可以枚举步数，然后再枚举向下走了几次，有点分层图的感觉。

/*
*/
#include<bits/stdc++.h> 
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define ll long long 
#define rg register 
#define pt(x) printf("%d ", x);
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 2001, inf = 1e9 + 10, mod = 1e9 + 7, b = 1;
const double eps = 1e-9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, k, vis[maxn][maxn], f[maxn][maxn];
char s[maxn][maxn];
int main() {
    n = read(); k = read();
    for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(s[i][j] == 'a') f[i][j]++;
            if(i + j - 1 - f[i][j] <= k) s[i][j] = 'a';
        }
    }
    putchar(s[1][1]); vis[1][1] = 1;
    for(int i = 3; i <= n << 1; i++) {//all step
        char now = 'z' + 1;
        for(int j = 1; j < i; j++) { // num of down
            if(j > n || (i - j > n)) continue;
            if(!vis[j - 1][i - j] && !vis[j][i - j - 1]) continue;
            now = min(now, s[j][i - j]);    
        }
        putchar(now);
        for(int j = 1; j < i; j++) { // num of down
            if(j > n || (i - j > n)) continue;
            if(!vis[j - 1][i - j] && !vis[j][i - j - 1]) continue;
            if(s[j][i - j] == now) vis[j][i - j] = 1;   
        }       
    }
    return 0;
}
/*

*/