专做废旧电子电路板配件回收的网站,正能量erp软件下载免费,app设计方案模板,视频网站做视频容易火1207. 大臣的旅费 - AcWing题库 很久以前#xff0c;TT 王国空前繁荣。 为了更好地管理国家#xff0c;王国修建了大量的快速路#xff0c;用于连接首都和王国内的各大城市。 为节省经费#xff0c;TT 国的大臣们经过思考#xff0c;制定了一套优秀的修建方案#xff0c;…1207. 大臣的旅费 - AcWing题库 很久以前TT 王国空前繁荣。 为了更好地管理国家王国修建了大量的快速路用于连接首都和王国内的各大城市。 为节省经费TT 国的大臣们经过思考制定了一套优秀的修建方案使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。 同时如果不重复经过大城市从首都到达每个大城市的方案都是唯一的。 JJ 是 TT 国重要大臣他巡查于各大城市之间体察民情。 所以从一个城市马不停蹄地到另一个城市成了 JJ 最常做的事情。 他有一个钱袋用于存放往来城市间的路费。 聪明的 JJ 发现如果不在某个城市停下来修整在连续行进过程中他所花的路费与他已走过的距离有关。 具体来说一段连续的旅途里第 11 千米的花费为 1111第 22 千米的花费为 1212第 33 千米的花费为 1313…第 xx 千米的花费为 x10x10。 也就是说如果一段旅途的总长度为 11 千米则刚好需要花费 1111如果一段旅途的总长度为 22 千米则第 11 千米花费 1111第 22 千米花费 1212一共需要花费 111223111223。 JJ 大臣想知道他从某一个城市出发中间不休息到达另一个城市所有可能花费的路费中最多是多少呢 输入格式 输入的第一行包含一个整数 nn表示包括首都在内的 TT 王国的城市数。 城市从 11 开始依次编号11 号城市为首都。 接下来 n−1n−1 行描述 TT 国的高速路TT 国的高速路一定是 n−1n−1 条。 每行三个整数 Pi,Qi,DiPi,Qi,Di表示城市 PiPi 和城市 QiQi 之间有一条双向高速路长度为 DiDi 千米。 输出格式 输出一个整数表示大臣 JJ 最多花费的路费是多少。 数据范围 1≤n≤1051≤n≤105, 1≤Pi,Qi≤n1≤Pi,Qi≤n, 1≤Di≤10001≤Di≤1000 输入样例 5 1 2 2 1 3 1 2 4 5 2 5 4 输出样例 135 1.
树的直径,树中两点之间的距离的最大值是多少?求这个值的做法是,先随便找一个点,然后找到距离该点最远距离的点A,再找到距离A点最远距离的点B,AB两点的距离就是最大直径.
2.
用dfs可以找到A点最远点B和对应的距离.
dfs遍历每一个点,对于每一个点都具有一个信息,距离A点的距离是多少,作为节点信息.
3.
用邻接表存储图的信息. 用一个vectorvectorp g;类型表示邻接表,外层vector下标表示每一个点,每一个点对应的vector存储pairint,int类型,表示从下标点可以走到的点和距离. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符using ppairint,int; // 定义 pairint, int 类型的别名为 pint n; // 城市数量
vectorvectorp g; // 邻接表表示的图int ret; // 存储最长路径长度
int lastpos; // 存储最长路径的终点
vectorboolvisited; // 访问标记数组// 深度优先搜索函数
void dfs(int i,int path){if(pathret)lastposi; // 如果当前路径长度大于已知最长路径更新终点位置retmax(ret,path); // 更新最长路径长度visited[i]true; // 标记当前节点已访问for(autox:g[i]){ // 遍历当前节点的邻接节点if(!(visited[x.first]))dfs(x.first,pathx.second); // 如果邻接节点未访问继续递归搜索}visited[i]false; // 回溯标记当前节点未访问
}// 初始化函数
void init(){ret0,lastpos0; // 初始化最长路径长度和终点位置visited.assign(n1,false); // 初始化访问标记数组}// 求解函数
void solve(){dfs(1,0); // 从节点 1 开始第一次深度优先搜索dfs(lastpos,0); // 从第一次搜索到的终点开始第二次深度优先搜索cout (ret * ret 21 * ret) / 2; // 输出结果计算最大花费
}// 主函数
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 加速输入输出cinn; // 输入城市数量g.assign(n1,vectorp()); // 初始化邻接表for(int i1;in-1;i){int start,end,length;cinstartendlength; // 输入每条边的信息g[start].push_back({end,length}); // 添加边到邻接表g[end].push_back({start,length}); // 添加边到邻接表双向}init(); // 调用初始化函数solve(); // 调用求解函数
}走出迷宫 链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 题目描述 小明现在在玩一个游戏游戏来到了教学关卡迷宫是一个N*M的矩阵。 小明的起点在地图中用“S”来表示终点用“E”来表示障碍物用“#”来表示空地用“.”来表示。 障碍物不能通过。小明如果现在在点xy处那么下一步只能走到相邻的四个格子中的某一个x1yx-1yxy1xy-1 小明想要知道现在他能否从起点走到终点。 输入描述: 本题包含多组数据。 每组数据先输入两个数字N,M 接下来N行每行M个字符表示地图的状态。 数据范围 2N,M500 保证有一个起点S同时保证有一个终点E. 输出描述: 每组数据输出一行如果小明能够从起点走到终点那么输出Yes否则输出No 示例1 输入 复制3 3 S.. ..E ... 3 3 S## ### ##E 3 3 S.. ..E ... 3 3 S## ##E 输出 复制Yes No Yes No 1.
迷宫从某一个点出发,寻找是否存在一条路径到达另一个指定点,只需要用dfs遍历所有的可以走的位置即可.
用一个visited存储可以走的路径和不可以走的路径,走过的路径是不可以走的位置.
2.
找某点到另一个点是否有路径,不需要回溯操作,回溯操作有点时候会导致时间复杂度变大.
这道题回溯会导致时间超时. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符using p pairint, int; // 定义 pairint, int 类型的别名为 p
p start, end1; // 定义起点和终点int n, m; // 定义迷宫的行数和列数
vectorvectorchar g; // 定义迷宫的矩阵vectorp d {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 定义四个移动方向右、下、左、上
vectorvectorbool visited; // 定义访问标记矩阵// 深度优先搜索函数判断是否能从起点到达终点
bool dfs(int i, int j) {if (i end1.first j end1.second) { // 如果当前点是终点返回 truereturn true;}visited[i][j] true; // 标记当前点已访问for (auto dd : d) { // 遍历四个方向int x i dd.first;int y j dd.second;if (x 0 x n y 0 y m !visited[x][y]) { // 判断新位置是否在边界内且未访问if (dfs(x, y)) return true; // 递归搜索如果找到路径返回 true}}// visited[i][j] false; // 不需要回溯return false; // 如果所有方向都无法到达终点返回 false
}// 初始化函数
void init() {visited.assign(n, vectorbool(m, false)); // 初始化访问标记矩阵for (int i 0; i n; i) {for (int j 0; j m; j) {if (g[i][j] #) visited[i][j] true; // 将障碍物标记为已访问}}
}// 求解函数
void solve() {if (dfs(start.first, start.second)) { // 从起点开始深度优先搜索cout Yes endl; // 如果可以到达终点输出 Yes} else {cout No endl; // 否则输出 No}
}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出while (cin n m) { // 输入迷宫的行数和列数g.assign(n, vectorchar(m)); // 初始化迷宫矩阵for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j]; // 输入迷宫的每个字符if (g[i][j] S) {start {i, j}; // 找到起点位置}if (g[i][j] E) {end1 {i, j}; // 找到终点位置}}}init(); // 调用初始化函数solve(); // 调用求解函数}
}石油采集 链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 题目描述 随着海上运输石油泄漏的问题一个新的有利可图的行业正在诞生那就是撇油行业。如今在墨西哥湾漂浮的大量石油吸引了许多商人的目光。这些商人们有一种特殊的飞机可以一瓢略过整个海面20米乘10米这么大的长方形。上下相邻或者左右相邻的格子不能斜着来当然这要求一瓢撇过去的全部是油如果一瓢里面有油有水的话那就毫无意义了资源完全无法利用。现在商人想要知道在这片区域中他可以最多得到多少瓢油。 地图是一个N×N的网络每个格子表示10m×10m的正方形区域每个区域都被标示上了是油还是水 输入描述: 测试输入包含多条测试数据 测试数据的第一行给出了测试数据的数目TT75 每个测试样例都用数字NN50来表示地图区域的大小接下来N行每行都有N个字符其中符号’.’表示海面、符号’#’表示油面。 输出描述: 输出格式如下“Case X: M”X从1开始M是商人可以最多得到的油量。 示例1 输入 复制1 6 ...... .##... ...... .#..#. .#..## ...... 1 6 ...... .##... ...... .#..#. .#..## ...... 输出 复制Case 1: 3 Case 1: 3 1.
找网格中具有多少个1x2的矩形,计算横纵坐标累加值的奇数和偶数的个数,具有的矩形个数是min(odd,even).
odd是奇数,even是偶数. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符
using ppairint,int; // 定义 pairint, int 类型的别名为 pvectorpd{{0,1},{1,0},{0,-1},{-1,0}}; // 定义四个移动方向右、下、左、上int t, n; // 测试数据的数量和地图区域的大小
vectorvectorchar g; // 定义地图矩阵int ret; // 记录最多可以撇油的数量
int even, odd; // 记录偶数和奇数格子的数量
int count11; // 记录测试用例编号// 深度优先搜索函数用于遍历油区域
void dfs(int i, int j) {if((ij)1) odd; // 如果 (ij) 是奇数oddelse even; // 否则 evenif(g[i][j]#) g[i][j].; // 将当前油格子标记为已访问for(auto dd : d) { // 遍历四个方向int x i dd.first;int y j dd.second;if(x 0 x n y 0 y n g[x][y] #) { // 判断新位置是否在边界内且是油dfs(x, y); // 递归搜索}}
}// 初始化函数
void init() {ret 0, even 0, odd 0; // 初始化变量
}// 求解函数
void solve() {for(int i 0; i n; i) {for(int j 0; j n; j) {even 0, odd 0; // 每次搜索前重置计数器if(g[i][j] #) dfs(i, j); // 如果当前格子是油开始深度优先搜索ret min(even, odd); // 取偶数和奇数中的最小值累加到结果中}}cout Case count1 : ret endl; // 输出结果
}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin t; // 输入测试数据的数量while(t--) { // 处理每组测试数据cin n; // 输入地图区域的大小g.assign(n, vectorchar(n)); // 初始化地图矩阵for(int i 0; i n; i) {for(int j 0; j n; j) {cin g[i][j]; // 输入地图的每个字符}}init(); // 调用初始化函数solve(); // 调用求解函数}
}after与迷宫 链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 题目描述 after的算法书的遗落在一个叫做AIJ的迷宫中了这个迷宫有N*M个房间迷宫的入口为(11)算法书遗落在(rc)。迷宫中的房间有四种状态空房间、无法进入的房间、有墨菲斯托存在的房间和有莉莉丝存在的房间。墨菲斯托会否定一切而莉莉丝会诱惑人做一种叫做YK的活动。after是一个意志薄弱的人他遇到了墨菲斯托和莉莉丝之后便会变成眼神空洞的超级YK机器人。after每步可以从他当前的房间走至上下左右四个房间的其中一个房间。after害怕变成超级YK机器人所以要尽快拿到算法书然后从入口逃离。问after最少需要走多少步才可以在不变成超级YK机器人的情况下从入口出发取回算法书并逃离迷宫 输入描述: 第一行一个正整数T(T10)表示共有T组数据。 对于每组数据第一行四个正整数NMrc(1N,M10001rN1cM)。 接下来N行每行M个字符每个表示房间的状态“.”表示空房间“*”表示无法进入的房间“F”表示有墨菲斯托存在的房间“M”表示有莉莉丝存在的房间。 数据保证(11)为“.”。 输出描述: 对每组数据输出一行即after最少需要走的步数。若after无法取回算法书则输出“IMPOSSIBLE”(不带引号)。 示例1 输入 复制1 4 4 4 3 ..** *F.. *.*. *M.F 1 4 4 4 3 ..** *F.. .. *M.F 输出 复制14 14 1.
不能够同时遇到F和M,所以有两种情况,允许遇到F或者允许遇到M.找最短的距离,从出发点前往魔法书的位置然后还需要返回到出发点,距离乘以2即可.
2.
bfs维护存储出发点到所有位置的最短距离. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符
using p pairint, int; // 定义 pairint, int 类型的别名为 pvectorp d {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 定义四个移动方向右、下、左、上int t; // 测试数据的数量
int n, m, r, c; // 地图的行数、列数以及算法书的位置vectorvectorchar g; // 定义地图矩阵
vectorvectorint dis1; // 定义从起点到各位置的最短距离矩阵允许遇到 F
vectorvectorint dis2; // 定义从起点到各位置的最短距离矩阵允许遇到 M
int ret; // 记录最终结果// 广度优先搜索函数用于计算最短路径
void bfs(vectorvectorint dis, char ch) {queuep q; // 定义队列用于 BFSq.push({0, 0}); // 从起点开始dis[0][0] 0; // 起点到自己的距离为 0while (!q.empty()) {auto top q.front(); // 获取队首元素q.pop(); // 弹出队首元素int i top.first, j top.second; // 当前坐标if (i r j c) return; // 如果到达目标位置返回for (auto dd : d) { // 遍历四个方向int x i dd.first;int y j dd.second;// 判断新位置是否在边界内且不是障碍物、指定角色且未被访问if (x 0 x n y 0 y m g[x][y] ! * g[x][y] ! ch dis[x][y] LLONG_MAX) {dis[x][y] dis[i][j] 1; // 更新新位置的距离q.push({x, y}); // 将新位置加入队列}}}
}// 初始化函数
void init() {ret 0; // 重置结果dis1.assign(n, vectorint(m, LLONG_MAX)); // 初始化距离矩阵设为无穷大dis2.assign(n, vectorint(m, LLONG_MAX)); // 初始化距离矩阵设为无穷大
}// 求解函数
void solve() {bfs(dis1, F); // 计算不遇到 F 的最短路径bfs(dis2, M); // 计算不遇到 M 的最短路径ret min(dis1[r][c], dis2[r][c]); // 取两种情况中的最短距离if (ret ! LLONG_MAX)cout 2 * ret endl; // 输出最短路径长度的两倍else cout IMPOSSIBLE endl; // 如果无法到达输出 IMPOSSIBLE
}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin t; // 输入测试数据的数量while (t--) { // 处理每组测试数据cin n m r c; // 输入地图的行数、列数以及算法书的位置r--, c--; // 将算法书位置调整为从 0 开始的索引g.assign(n, vectorchar(m)); // 初始化地图矩阵for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j]; // 输入地图的每个字符}}init(); // 调用初始化函数solve(); // 调用求解函数}
}逃离迷宫 链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网 题目描述 给你一个n*m的图地图上.代表可以走的地方而#代表陷阱不能走 P代表人物位置K代表钥匙E代表出口。人物一个钥匙有多个 K的数量50),出口一个每个位置可以向上下左右四个 方向走一格花费一个单位时间现在你需要花费最少的时间拿到钥匙 然后从迷宫的出口出去(若没有钥匙则不能进入迷宫出口所在的格子)。 输入描述: 第一行一个整数T(T 50)代表数据的组数 接下来一行n,m(n500,m500),代表地图的行和列 接下来n行每行一个长度为m的字符串组成一个图。 输出描述: 如果可以出去输出所花费的最少时间。 如果不能出去输出一行No solution。 示例1 输入 复制3 5 5 ....P ##..E K#... ##... ..... 5 5 P.... ..... ..E.. ..... ....K 5 5 P#..E .#.#. .#.#. .#.#. ...#K 3 5 5 ....P ##..E K#... ##... ..... 5 5 P.... ..... ..E.. ..... ....K 5 5 P#..E .#.#. .#.#. .#.#. ...#K 输出 复制No solution 12 No solution No solution 12 No solution 1.
入口,钥匙点,出口,我们需要从入口到达其中一个钥匙点,然后去出口,求最短的距离.
存储入口到所有位置的最短距离,和出口到所有位置的最短距离,遍历每一个钥匙点,如果距离存在,找最短就可以了. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符
using p pairint, int; // 定义 pairint, int 类型的别名为 pvectorp d {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 定义四个移动方向右、下、左、上int t, n, m; // t 为测试数据的数量n 为地图的行数m 为地图的列数
vectorvectorchar g; // 定义地图矩阵vectorvectorint dis1; // 定义从起点到各位置的最短距离矩阵
vectorvectorint dis2; // 定义从出口到各位置的最短距离矩阵
p start, end1; // 定义起点和终点
int ret; // 记录最终结果
vectorp yaoshi; // 定义钥匙的位置列表// 广度优先搜索函数用于计算最短路径
void bfs(vectorvectorint dis, p point) {dis[point.first][point.second] 0; // 起点距离为 0queuep q; // 定义队列用于 BFSq.push(point); // 将起点加入队列while (!q.empty()) {auto top q.front(); // 获取队首元素q.pop(); // 弹出队首元素int i top.first; // 当前坐标int j top.second; // 当前坐标if (point start i end1.first j end1.second) continue; // 如果是起点且到达终点继续for (auto dd : d) { // 遍历四个方向int x i dd.first; // 新位置的行坐标int y j dd.second; // 新位置的列坐标// 判断新位置是否在边界内且不是陷阱且未被访问if (x 0 x n y 0 y m g[x][y] ! # dis[x][y] LLONG_MAX) {q.push({x, y}); // 将新位置加入队列dis[x][y] dis[i][j] 1; // 更新新位置的距离}}}
}// 初始化函数
void init() {dis1.assign(n, vectorint(m, LLONG_MAX)); // 初始化距离矩阵设为无穷大dis2.assign(n, vectorint(m, LLONG_MAX)); // 初始化距离矩阵设为无穷大ret LLONG_MAX; // 初始化结果为无穷大
}// 求解函数
void solve() {bfs(dis1, start); // 计算从起点到各位置的最短路径bfs(dis2, end1); // 计算从出口到各位置的最短路径for (auto x : yaoshi) { // 遍历所有钥匙位置int i x.first; // 钥匙的行坐标int j x.second; // 钥匙的列坐标// 判断起点到钥匙和出口到钥匙的距离是否存在if (dis1[i][j] ! LLONG_MAX dis2[i][j] ! LLONG_MAX) {ret min(ret, dis1[i][j] dis2[i][j]); // 更新最短路径}}if (ret ! LLONG_MAX) cout ret endl; // 输出最短路径else cout No solution endl; // 如果无法到达输出 No solution
}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin t; // 输入测试数据的数量while (t--) { cin n m; // 输入地图的行数和列数g.assign(n, vectorchar(m)); // 初始化地图矩阵yaoshi.clear(); // 清空钥匙列表for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j]; // 输入地图的每个字符if (g[i][j] P) { // 如果是人物位置start.first i;start.second j;}if (g[i][j] E) { // 如果是出口位置end1.first i;end1.second j;}if (g[i][j] K) { // 如果是钥匙位置yaoshi.push_back({i, j});}}}init(); // 调用初始化函数solve(); // 调用求解函数}return 0;
}3205. 最优配餐 - AcWing 题库 栋栋最近开了一家餐饮连锁店提供外卖服务。 随着连锁店越来越多怎么合理的给客户送餐成为了一个急需解决的问题。 栋栋的连锁店所在的区域可以看成是一个 n×nn×n 的方格图如下图所示方格的格点上的位置上可能包含栋栋的分店绿色标注或者客户蓝色标注有一些格点是不能经过的红色标注。 方格图中的线表示可以行走的道路相邻两个格点的距离为 11。 栋栋要送餐必须走可以行走的道路而且不能经过红色标注的点。 送餐的主要成本体现在路上所花的时间每一份餐每走一个单位的距离需要花费 11 块钱。 每个客户的需求都可以由栋栋的任意分店配送每个分店没有配送总量的限制。 现在你得到了栋栋的客户的需求请问在最优的送餐方式下送这些餐需要花费多大的成本。 输入格式 输入的第一行包含四个整数 n,m,k,dn,m,k,d分别表示方格图的大小、栋栋的分店数量、客户的数量以及不能经过的点的数量。 接下来 mm 行每行两个整数 xi,yixi,yi表示栋栋的一个分店在方格图中的横坐标和纵坐标。 接下来 kk 行每行三个整数 xi,yi,cixi,yi,ci分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。注意可能有多个客户在方格图中的同一个位置 接下来 dd 行每行两个整数分别表示每个不能经过的点的横坐标和纵坐标。 输出格式 输出一个整数表示最优送餐方式下所需要花费的成本。 数据范围 前 30%30% 的评测用例满足1≤n≤201≤n≤20。 前 60%60% 的评测用例满足1≤n≤1001≤n≤100。 所有评测用例都满足1≤n≤1000,1≤m,k,d≤n2,1≤xi,yi≤n1≤n≤1000,1≤m,k,d≤n2,1≤xi,yi≤n。 可能有多个客户在同一个格点上。 每个客户的订餐量不超过 10001000每个客户所需要的餐都能被送到。 输入样例 10 2 3 3 1 1 8 8 1 5 1 2 3 3 6 7 2 1 2 2 2 6 8 输出样例 29 1.
多源最短路径,我们要求客户点距离多个商家位置的最短距离,例如客户点A距离商家B,C最短距离.
将B,C点依次加入到队列中,然后bfs维护数据距离.
2.
用dis存储每一个点到达某一个商家点的最短距离,遍历所有的客户点,距离乘以订单数即可. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符
using p pairint, int; // 定义 pairint, int 类型的别名为 pvectorp d1 {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 定义四个移动方向右、下、左、上int n, m, k, d; // n 为方格图的大小m 为分店数量k 为客户数量d 为不能经过的点的数量
vectorp fendian; // 定义分店位置列表
struct node { // 定义客户节点结构体int x, y; // 客户的坐标int count; // 客户的订餐量
};
vectornode kehu; // 定义客户列表
vectorvectorint dis; // 定义距离矩阵
int ret; // 记录最终结果// 广度优先搜索函数用于计算最短路径
void bfs() {queuep q; // 定义队列用于 BFSfor (auto xx : fendian) { // 将所有分店位置加入队列q.push(xx);dis[xx.first][xx.second] 0; // 分店位置距离自身为 0}while (!q.empty()) {auto top q.front(); // 获取队首元素q.pop(); // 弹出队首元素int i top.first; // 当前坐标int j top.second; // 当前坐标for (auto dd : d1) { // 遍历四个方向int x i dd.first; // 新位置的行坐标int y j dd.second; // 新位置的列坐标// 判断新位置是否在边界内且未被访问if (x 0 x n y 0 y n dis[x][y] -1) {q.push({x, y}); // 将新位置加入队列dis[x][y] dis[i][j] 1; // 更新新位置的距离}}}
}// 求解函数
void solve() {bfs(); // 调用 BFS 函数计算最短路径for (auto xx : kehu) { // 遍历所有客户ret dis[xx.x][xx.y] * xx.count; // 计算每个客户的配送成本并累加}cout ret endl; // 输出最终结果
}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin n m k d; // 输入方格图的大小、分店数量、客户数量以及不能经过的点的数量fendian.assign(m, p()); // 初始化分店列表kehu.assign(k, node()); // 初始化客户列表dis.assign(n, vectorint(n, -1)); // 初始化距离矩阵设为 -1for (int i 0; i m; i) {cin fendian[i].first fendian[i].second; // 输入每个分店的位置fendian[i].first--; // 将坐标转换为从 0 开始fendian[i].second--;}for (int i 0; i k; i) {cin kehu[i].x kehu[i].y kehu[i].count; // 输入每个客户的位置及订餐量kehu[i].x--; // 将坐标转换为从 0 开始kehu[i].y--;}for (int i 0; i d; i) {int x, y;cin x y; // 输入每个不能经过的点的位置x--, y--; // 将坐标转换为从 0 开始dis[x][y] LLONG_MAX; // 将不能经过的点标记为无穷大}solve(); // 调用求解函数return 0;
}路径之谜 题目描述 小明冒充X星球的骑士,进入了一个奇怪的城堡。 城堡里边什么都没有,只有方形石头铺成的地面。 假设城堡地面是nxn个方格。如下图所示 按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃,每走到一个新方格,就要向正北方和正西方各射一箭。(城堡 的西墙和北墙内各有12个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时 是可以的,比如上图中的例子。 本题的要求就是已知简靶数字,求骑士的行走路径(测试数据保证路径唯一 输入描述 第一行一个整数N(0N20),表示地面有NXN个方格。 第二行N个整数,空格分开,表示北边的箭靶上的数字(自西向东) 第三行N个整数,空格分开,表示西边的箭靶上的数字(自北向南) 输出描述 输出一行若干个整数,表示骑士路径。 为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号号:0,1,2,3- 比如,上图中的方块编号为: 0123 4567 891011 12131415 输入输出样例 示例 输入 4333 输出 045123711109131415 运行限制 最大运行时间:5s 最大运行内存:256M 1.
网格(i,j)坐标转化为数字的公式是i*colj.
dfs遍历网格每一个点,到达每一个点的时候维护节点的信息.
节点信息,是所走路径导致的靶子上箭的数量.
2.
剪枝操作,当维护当前节点箭数量之后,当前箭数量大于对应目标箭数量,此时不需要再继续了,因为箭的数量只能增加不能减少.
如果到达了终点,箭数量有一个不对,就返回.
3.
goto flag1;
flag1:
组合起来可以传送操作. #includebits/stdc.h
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl \n // 定义换行符
using p pairint, int; // 定义 pairint, int 类型的别名为 pvectorp d {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 定义四个移动方向右、下、左、上int n; // 定义地面的大小 n*n
vectorint aim1; // 北边的箭靶上的数字
vectorint aim2; // 西边的箭靶上的数字vectorint nowaim1; // 当前北边的箭数量
vectorint nowaim2; // 当前西边的箭数量
vectorint path; // 记录骑士的路径
vectorvectorbool visited; // 记录每个方格是否被访问// 深度优先搜索函数判断是否可以通过当前路径到达终点
bool dfs(int i, int j) {visited[i][j] true; // 标记当前方格已访问nowaim1[j]; // 当前列的箭数量加一nowaim2[i]; // 当前行的箭数量加一path.push_back(i * n j); // 将当前方格编号加入路径// 剪枝如果当前箭数量超过目标箭数量回溯if (nowaim1[j] aim1[j] || nowaim2[i] aim2[i]) goto flag1;// 如果到达终点检查所有箭数量是否符合目标if (i n - 1 j n - 1) {for (int k 0; k n; k) {if (nowaim1[k] ! aim1[k] || nowaim2[k] ! aim2[k]) goto flag1;}return true; // 路径符合要求返回 true}// 继续搜索四个方向for (auto xx : d) {int x i xx.first;int y j xx.second;if (x 0 x n y 0 y n !visited[x][y]) {if (dfs(x, y)) return true; // 如果找到路径返回 true}}// 回溯操作flag1:nowaim1[j]--;nowaim2[i]--;visited[i][j] false;path.pop_back();return false; // 返回 false表示当前路径不符合要求
}// 求解函数
void solve() {dfs(0, 0); // 从起点开始深度优先搜索for (auto x : path) {cout x ; // 输出路径}cout endl;
}// 主函数
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出cin n; // 输入地面的大小aim1.assign(n, 0); // 初始化北边的箭靶数字aim2.assign(n, 0); // 初始化西边的箭靶数字nowaim1.assign(n, 0); // 初始化当前北边的箭数量nowaim2.assign(n, 0); // 初始化当前西边的箭数量visited.assign(n, vectorbool(n, false)); // 初始化访问矩阵for (int i 0; i n; i) cin aim1[i]; // 输入北边的箭靶数字for (int i 0; i n; i) cin aim2[i]; // 输入西边的箭靶数字solve(); // 调用求解函数
}结尾
最后感谢您阅读我的文章希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点请随时在评论区留言。 同时不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中我将继续探讨这个话题的不同方面为您呈现更多深度和见解。 谢谢您的支持期待与您在下一篇文章中再次相遇
