蓝桥杯——16

news/2024/6/23 18:36:32

学习视频: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
*/

Q:生日蛋糕

放弃了,好难!


https://www.xjx100.cn/news/3380558.html

相关文章

头歌-机器学习 第13次实验 特征工程——共享单车之租赁需求预估

第1关&#xff1a;数据探索与可视化 任务描述 本关任务&#xff1a;编写python代码&#xff0c;完成一天中不同时间段的平均租赁数量的可视化功能。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 读取数据数据探索与可视化 读取数据 数据保存在./step1/…

海山数据库(He3DB)原理剖析:浅析OLAP数据库计算引擎中的统计信息

背景&#xff1a; 统计信息在计算引擎的优化器模块中经常被提及&#xff0c;尤其是在基于成本成本优化&#xff08;CBO&#xff09;框架中统计信息发挥着至关重要的作用。CBO旨在通过评估执行查询的可能方法&#xff0c;并选择最有效的执行计划来提高查询性能。而统计信息则提…

外包干了3天,技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入杭州某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…

初识--数据结构

什么是数据结构&#xff1f;我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了&#xff0c;学习C语言不就够了吗&#xff1f;为什么还要学习数据结构呢&#xff1f;这是因为&#xff1a;数据结构能够解决C语言解决不了的问题&#xff0…

位图布隆过滤器的原理及实现

目录 位图的概念&#xff1a; 位图的前置知识&#xff1a;位运算 位图的实现&#xff1a; 位图的基本参数和构造方法&#xff1a; 位图的插入&#xff1a; 位图的查找&#xff1a; 位图的删除&#xff1a; 布隆过滤器概念&#xff1a; 布隆过滤器的实现&#xff1a; …

NLopt

非线性优化–NLopt (nonlinear optimization)是一个免费的开源的库&#xff0c;提供了很多种非线性优化算的使用接口。 1、其中非常大的优势就是提供多种支持的语言&#xff0c;包括C/ C/ Julia/ Python/ R/ Fortran/ Lua/ OCaml/ Octave等都支持 1. 区别 **COBYLA&#xff0…

蓝桥杯C/C++A组省赛历年真题题解(2020~2023)

刷题整理2020~2023蓝桥A组真题。 2020202120222023门牌制作卡片&#xff08;模拟题&#xff09;裁纸刀幸运数既约分数直线&#xff08;数学枚举&#xff09;灭鼠先锋有奖问答蛇形填数货物摆放(因子暴力枚举&#xff09;求和平方差七段码路径(最短路)选数异或更小的数平面分割回…

前端三剑客 —— JavaScript (第八节)

内容回顾&#xff1a; 事件对象 1.1 什么是事件驱动 1.2 事件绑定 事件源&#xff1a;发生事件的源对象 事件对象&#xff1a;它包含了事件所有的信息&#xff0c;它是以回调函数的第一个参数形式出现的&#xff08;event&#xff09; 事件处理函数&#xff1a;也叫回调函数&a…