蓝桥杯——16

学习视频：17-深搜的剪枝策略视频讲解_哔哩哔哩_bilibili

#include<iostream>
#include<cstring>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int ans = 100000;
bool in(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x, int y, int step) {//剪枝if (step >= ans) return;if (maze[x][y] == 'T') {ans = step;return;}vis[x][y] = 1;int fx, fy;for (int i = 0; i < 4; i++) {fx = x + dir[i][0];fy = y + dir[i][1];if (in(fx, fy) && !vis[fx][fy] && maze[fx][fy] != '*') {dfs(fx, fy, step + 1);}}vis[x][y] = 0;
}
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> maze[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (maze[i][j] == 'S')dfs(i, j, 0);}}cout << ans << endl;return 0;
}
/*
3 4
S**.
....
***T
*/

Q：k个数的和

#include<iostream>
#include<cstring>
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
void dfs(int s, int cnt, int pos) {//剪枝if (s > sum || cnt > k) {return;}if (s == sum && cnt == k) {ans++;}for (int i = pos; i < n; i++) {if (!xuan[i]) {xuan[i] = 1;dfs(s + a[i], cnt + 1, i+1);xuan[i] = 0;}}}
int main() {n = 30;k = 8;sum = 200;for (int i = 0; i < 30; i++) {a[i] = i + 1;}dfs(0, 0, 0);cout << ans;return 0;
}

Q：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
int n, m, T;
char mat[N][N];
bool vis[N][N];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool ok;
void dfs(int x, int y, int t) {if (ok) return;if (t = T) {if (mat[x][y] == 'D') ok = true;return;}vis[x][y] = true;for (int i = 0; i < 4; i++) {int tx = x + dx[i];int ty = y + dy[i];if (tx < 0 || ty < 0 || tx >= n || ty >= m || mat[tx][ty] == 'X')continue;dfs(tx, ty, t + 1);}vis[x][y] = false;
}int main() {cin >> n >> m >> T;for (int i = 0; i < n; i++) {cin >> mat[i];}int sx, sy, ex, ey;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mat[i][j] == 'S') sx = i, sy = j;if (mat[i][j] == 'D')ex = i, ey = j;}}if ((sx + sy + ex + ey + T) % 2 != 0) {cout << "NO" << endl;}else {ok = false;dfs(sx, sy, 0);if (ok)cout << "YES" << '\n';elsecout << "NO" << endl;}return 0;
}
/*
4 4 5
S.X.
..X.
..XD
....
*/

Q:引爆炸弹

#include<iostream>
#include<cstring>
using namespace std;
char mat[1010][1010];
int n, m;
bool row[1010], col[1010];
void boom(int x, int y) {mat[x][y] = 0;if (!row[x]) {row[x] = true;for (int i = 0; i < m; i++) {if (mat[x][i] == '1')boom(x, i);}}if (!col[y]) {col[y] = true;for (int i = 0; i < n; i++) {if (mat[i][y] == '1')boom(i, y);}}
}int main() {int cnt = 0;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> mat[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mat[i][j] == '1') {boom(i, j);cnt++;}}}cout << cnt;return 0;
}
/*
5 5
00010
00010
01001
10001
01000
*/