蓝桥杯——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';
		else
			cout << "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
*/

Q:生日蛋糕

放弃了，好难！