dfs，对每个当前层的g进行长草，并且长出来的草都是下一层可以长的草

#include<iostream> using namespace std; const int N = 1010; int n, m, k; int
ed[N][N]; char st[N][N]; bool check(){ for(int i = 1; i <= n; i++) for(int j =
1; j <= m; j++) if(ed[i][j] == 0) return true; return false; } void dfs(int u,
int v, int d){ int dx[] = {0, 0, -1, 1}; int dy[] = {1, -1, 0, 0}; for(int i =
0; i < 4; i++){ int x = dx[i] + u, y = dy[i] + v; if(x >= 1 && y >= 1 && x <= n
&& y <= m && st[x][y] == '.'){ st[x][y] = 'g'; ed[x][y] = d; } } } int main(){
scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
cin>>st[i][j]; ed[i][j] = 1; } scanf("%d", &k); int x = 1; //第一层 while(x <= k){
if(check()) break; //全变为g不用再搜索了 for(int i = 1; i <= n; i++) for(int j = 1; j <=
m; j++) if(st[i][j] == 'g' && ed[i][j] == x) dfs(i, j, x + 1); x++; } for(int i
= 1; i <= n; i++){ for(int j = 1; j <= m; j++) printf("%c", st[i][j]);
puts(""); } return 0; }

L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。

f[i, j] 表示从a里面选前i个数，和从b里面选前j个数，构成的最长长度

*
a[i] ！= b[j] f[i][j] = max(f[i-1][j], f[i][j-1]), 等于最大的a上一个长度，或者b上一个长度

*
a[i] == b[j] f[i][j] = max(f[i][j], f[i-1][j-1] + 1), 等于最大的本身和a,b上一个加一

#include<iostream> #include<vector> using namespace std; const int N = 1010;
string a[N], b[N]; int f[N][N]; int main(){ string s1, s2; cin>>s1; cin>>s2;
string str = ""; int n = s1.size(), m = s2.size(); int k = 1; for(int i = 0; i
< n; i++){ if(i > 0 && s1[i] >= 'A' && s1[i] <= 'Z'){ a[k++] = str; str = ""; }
if(i == n - 1) { str += s1[i]; a[k++] = str; str = ""; break; } str += s1[i]; }
n = k - 1; k = 1; for(int i = 0; i < m; i++){ if(i > 0 && s2[i] >= 'A' && s2[i]
<= 'Z'){ b[k++] = str; str = ""; } if(i == m - 1) { str += s2[i]; b[k++] = str;
str = ""; break; } str += s2[i]; } m = k - 1; for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){ f[i][j] = max(f[i-1][j], f[i][j-1]); if(a[i] ==
b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1); } cout<<f[n][m]<<endl; return 0;
}

#include<iostream> #include<queue> #include<cstring> using namespace std;
const int N = 1010; int d[N][N], vis[N][N][15]; int n, k; char g[N][N]; int
dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; struct node{ int x, y, k; node
(int ax, int ay, int ak){ x = ax, y = ay, k = ak; } }; int bfs(){ queue<node>
q; vis[1][1][0] = 1; q.push({1, 1, 0}); while(!q.empty()){ auto t = q.front();
q.pop(); if(t.x == n && t.y == n) return d[n][n]; for(int i = 0; i < 4; i++){
int x = dx[i] + t.x, y = dy[i] + t.y; if(x < 1 || x > n && y < 1 || y > n ||
g[x][y] == '#') continue; if(g[x][y] == '%' && !vis[x][y][k]){ vis[x][y][k] =
1; d[x][y] = d[t.x][t.y] + 1; q.push(node{x, y, k}); } else{ if(t.k &&
!vis[x][y][t.k - 1]){ vis[x][y][t.k - 1] = 1; d[x][y] = d[t.x][t.y] + 1;
q.push(node{x, y, t.k - 1}); } else if(g[x][y] == '.' && !t.k &&
!vis[x][y][0]){ vis[x][y][0] = 1; d[x][y] = d[t.x][t.y] + 1; q.push(node{x, y,
0}); } } } } return -1; } int main(){ scanf("%d%d", &n, &k); for(int i = 1; i
<= n; i++) for(int j = 1; j <= n; j++) cin>>g[i][j]; cout<<bfs()<<endl; return
0; }

GitHub

Gitee