当前位置: 首页 > news >正文

杭电oj(1010、1015、1241)题解

题解由豆包提供 

目录

​编辑

1010

题目

思路

整体思路概述

代码具体步骤分析

1. 变量和数组定义

2. 深度优先搜索函数 dfs

3. 主函数 main

总结

代码

1015

题目

思路

整体思路概括

代码各部分详细思路

1. 全局变量的定义

2. 深度优先搜索函数 dfs

3. 主函数 main

总结

代码

1241

题目

思路

整体思路概述

代码各部分详细思路

1. 全局变量和方向数组定义

2. 深度优先搜索函数 dfs

3. 主函数 main

总结

代码


1010

题目

思路

奇偶剪枝

这道题主要是剪枝的使用,可以通过单击上述奇偶剪枝去了解一下,普通的剪枝会超时。

整体思路概述

通过深度优先搜索遍历迷宫中的所有可能路径,同时利用奇偶剪枝和可通行区域判断进行优化,减少不必要的搜索,提高算法效率。

代码具体步骤分析

1. 变量和数组定义
const int LEN = 10;
char map[LEN][LEN];
bool flag;
int N, M, T;
int sx, sy, ex, ey;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
  • LEN:定义地图的最大长度。
  • map:二维字符数组,用于存储迷宫地图,其中 'S' 表示起点,'D' 表示终点,'X' 表示障碍物,'.' 表示可通行区域。
  • flag:布尔变量,用于标记是否找到了满足条件的路径。
  • N 和 M:分别表示迷宫的行数和列数。
  • T:表示允许的最大时间步数。
  • sx 和 sy:起点的坐标。
  • ex 和 ey:终点的坐标。
  • dx 和 dy:方向数组,用于表示上下左右四个方向的偏移量。
2. 深度优先搜索函数 dfs

void dfs(int x, int y, int time) {if (x < 0 || x >= N || y < 0 || y >= M) {return;}if (x == ex && y == ey && time == T) {flag = true;return;}// 奇偶剪枝int temp = T - time - abs(x - ex) - abs(y - ey); if (temp < 0 || temp % 2 == 1) return;for (int i = 0; i < 4; i++) {int mx = x + dx[i];int my = y + dy[i];if (map[mx][my] != 'X') {map[mx][my] = 'X';dfs(mx, my, time + 1);map[mx][my] = '.';if (flag) return;}}
}

  • 边界检查:如果当前位置超出迷宫边界,直接返回。
  • 终点判断:如果当前位置是终点且所用时间等于 T,则将 flag 置为 true 表示找到了满足条件的路径,并返回。
  • 奇偶剪枝:计算剩余时间与当前位置到终点的曼哈顿距离的差值 temp,如果 temp 小于 0 或者为奇数,则说明无法在 T 时间内到达终点,直接返回。
  • 递归搜索:遍历当前位置的上下左右四个相邻位置,如果相邻位置不是障碍物,则将该位置标记为已访问(map[mx][my] = 'X'),然后递归调用 dfs 函数继续搜索,搜索完成后将该位置恢复为可通行(map[mx][my] = '.')。如果已经找到了满足条件的路径(flag 为 true),则直接返回。
3. 主函数 main

int main() {while (cin >> N >> M >> T) {if (N == 0 && M == 0 && T == 0) break;flag = false;int ans = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> map[i][j];if (map[i][j] == 'S') {sx = i;sy = j;}if (map[i][j] == 'D') {ex = i;ey = j;}if (map[i][j] == 'X') {ans++;}}}if (N * M - ans <= T) {cout << "NO" << endl;continue;}map[sx][sy] = 'X';dfs(sx, sy, 0);if (flag) cout << "YES" << endl;else cout << "NO" << endl; }return 0;
}

  • 输入处理:循环读取迷宫的行数 N、列数 M 和允许的最大时间步数 T,当输入为 0 0 0 时结束循环。
  • 地图初始化:读取迷宫地图,记录起点和终点的坐标,并统计障碍物的数量。
  • 可通行区域判断:计算可通行区域的数量(N * M - ans),如果可通行区域的数量小于等于 T,则说明无法在 T 时间内到达终点,输出 NO 并继续下一组输入。
  • 标记起点:将起点标记为已访问(map[sx][sy] = 'X')。
  • 深度优先搜索:从起点开始调用 dfs 函数进行搜索。
  • 输出结果:根据 flag 的值输出 YES 或 NO

总结

通过深度优先搜索算法遍历迷宫中的所有可能路径,同时利用奇偶剪枝和可通行区域判断进行优化,避免了不必要的搜索,提高了算法的效率。

代码

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;const int LEN = 10;
char map[LEN][LEN];
bool flag;
int N, M, T;
int sx, sy, ex, ey;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y,int time){if(x<0 || x>=N || y<0 || y>=M){return;}if(x==ex && y==ey && time==T){flag=true;return;}//奇偶剪枝 int temp = T - time - abs(x - ex) - abs(y - ey); if (temp < 0 || temp % 2 == 1) return;for(int i=0;i<4;i++){int mx=x+dx[i];int my=y+dy[i];if(map[mx][my]!='X'){map[mx][my]='X';dfs(mx,my,time+1);map[mx][my]='.';if(flag) return;}}
}
int main(){while(cin>>N>>M>>T){if(N==0&&M==0&&T==0) break;flag=false;int ans=0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){cin>>map[i][j];if(map[i][j]=='S'){sx=i;sy=j;}if(map[i][j]=='D'){ex=i;ey=j;}if(map[i][j]=='X'){ans++;}}}if(N*M-ans<=T){cout<<"NO"<<endl;continue;}map[sx][sy]='X';dfs(sx,sy,0);if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl; }return 0;
}

1015

题目

思路

这段 C++ 代码的核心思路是利用深度优先搜索(DFS)算法,从给定字符串 s 里找出长度为 5 的字符组合,使得这些字符对应的数值按照特定数学公式 a - b * b + c * c * c - d * d * d * d + e * e * e * e * e 计算的结果等于给定的整数 n,并且要输出字典序最大的满足条件的组合。下面详细剖析代码的具体思路:

整体思路概括

借助深度优先搜索来生成所有可能的长度为 5 的字符组合,对每个组合计算数学表达式的值,若结果等于 n 且字典序比当前记录的结果大,就更新结果。最终输出满足条件的字典序最大的组合,若不存在则输出 "no solution"

代码各部分详细思路

1. 全局变量的定义

int n;
string s;
string ans;
bool used[13];

  • n:用于存储输入的目标整数,也就是数学表达式需要计算得到的结果。
  • s:存储输入的字符串,从这个字符串中选取字符组成长度为 5 的组合。
  • ans:用于记录满足条件的字典序最大的字符组合。
  • used:布尔类型数组,长度为 13,用来标记字符串 s 中的每个字符是否已经在当前组合中被使用。
2. 深度优先搜索函数 dfs

void dfs(int depth, string current) {if (depth == 5) {int a = current[0] - 'A' + 1;int b = current[1] - 'A' + 1;int c = current[2] - 'A' + 1;int d = current[3] - 'A' + 1;int e = current[4] - 'A' + 1;if (a - b * b + c * c * c - d * d * d * d + e * e * e * e * e == n) {if (current > ans) {ans = current;}}return;}for (int i = 0; i < s.size(); i++) {if (!used[i]) {used[i] = true;dfs(depth + 1, current + s[i]);used[i] = false;}}
}

  • 递归终止条件:当 depth 等于 5 时,意味着已经生成了一个长度为 5 的字符组合。将组合中的每个字符转换为对应的数值('A' 对应 1,'B' 对应 2,以此类推),计算数学表达式 a - b * b + c * c * c - d * d * d * d + e * e * e * e * e 的值。若结果等于 n 且该组合的字典序比当前的 ans 大,就更新 ans
  • 递归搜索过程:遍历字符串 s,若字符 s[i] 未被使用,将其标记为已使用,把该字符添加到当前组合 current 中,然后递归调用 dfs 函数,深度 depth 加 1。递归返回后,将该字符标记为未使用,以便后续生成其他组合时可以再次使用。
3. 主函数 main

int main() {while (cin >> n >> s) {ans = "";if (n == 0 || s == "END") break;fill(used, used + 13, false);dfs(0, "");if (ans.empty()) {cout << "no solution" << endl;}else cout << ans << endl;}return 0;
}

  • 输入处理:通过 while 循环持续读取输入的整数 n 和字符串 s,当 n 为 0 或者 s 为 "END" 时,结束输入。
  • 初始化操作:每次读取新的输入后,将 ans 清空,把 used 数组的所有元素初始化为 false,表示所有字符都未被使用。
  • 深度优先搜索:调用 dfs 函数,从深度 0 和空组合开始搜索。
  • 输出结果:若 ans 为空,说明没有找到满足条件的组合,输出 "no solution";否则输出 ans

总结

该代码通过深度优先搜索算法生成所有可能的长度为 5 的字符组合,对每个组合进行计算和比较,最终输出满足条件的字典序最大的组合。在搜索过程中,使用 used 数组确保每个字符仅被使用一次。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
string s;
string ans;
bool used[13];// 深度优先搜索函数
void dfs(int depth, string current) {if(depth==5){int a=current[0]-'A'+1;int b=current[1]-'A'+1;int c=current[2]-'A'+1;int d=current[3]-'A'+1;int e=current[4]-'A'+1;if (a - b * b + c * c * c - d * d * d * d + e * e * e * e * e == n) {if (current > ans) {ans = current;}}return;} for(int i=0;i<s.size();i++){if(!used[i]){used[i]=true;dfs(depth+1,current+s[i]);used[i]=false;}}
}int main() {while(cin>>n>>s){ans="";if(n==0 || s=="END") break;fill(used,used+13,false);dfs(0,"");if(ans.empty()){cout<<"no solution"<<endl;}else cout<<ans<<endl;}return 0;
}   

1241

题目

思路

这段代码的主要思路是使用深度优先搜索(DFS)算法来解决一个油田计数问题。具体来说,代码会统计一个由字符 @ 和其他字符组成的二维地图中,相连的 @ 字符所形成的油田的数量。下面详细阐述代码的思路:

整体思路概述

通过深度优先搜索遍历地图中的每个位置,当遇到 @ 字符时,将其作为一个新的油田的起始点,调用 DFS 函数将该油田的所有 @ 字符标记为已访问,同时油田数量加 1。最终输出地图中油田的总数。

代码各部分详细思路

1. 全局变量和方向数组定义
int dx[9]={0,-1,-1,0,1,1,1,0,-1};
int dy[9]={0,0,1,1,1,0,-1,-1,-1};
char map[105][105];
int n,m;

  • dx 和 dy:这两个数组构成了一个方向数组,用于表示当前位置的 8 个相邻位置(包括上、下、左、右、左上、右上、左下、右下)以及自身位置(dx[0]=0 和 dy[0]=0 表示自身)。
  • map:一个二维字符数组,用于存储地图信息,其中 @ 表示油田,其他字符表示非油田区域。
  • n 和 m:分别表示地图的行数和列数。
2. 深度优先搜索函数 dfs
void dfs(int x, int y) {map[x][y]='*';for(int i = 0; i < 9; i++) {if(dx[i] == 0 && dy[i] == 0) continue;int mx = x + dx[i];int my = y + dy[i];if(mx >= 0 && mx < n && my >= 0 && my < m && map[mx][my] == '@') {dfs(mx, my);}}
}

  • 标记当前位置:将当前位置 (x, y) 的字符标记为 *,表示该位置已被访问。
  • 遍历相邻位置:通过 dx 和 dy 数组遍历当前位置的 8 个相邻位置。如果 dx[i] 和 dy[i] 都为 0,说明是当前位置自身,跳过该情况。
  • 边界检查和递归调用:对于每个相邻位置 (mx, my),检查其是否在地图范围内(mx >= 0 && mx < n && my >= 0 && my < m),并且是否为 @ 字符。如果满足条件,则递归调用 dfs 函数继续搜索该相邻位置。
3. 主函数 main
int main() {int sum;while(cin >> n >> m) {if(n == 0 || m == 0) break;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {cin >> map[i][j];}}sum = 0;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(map[i][j] == '@') {dfs(i, j);sum++;}}}cout << sum << endl;}return 0;
}

  • 输入处理:通过 while 循环不断读取地图的行数 n 和列数 m,当 n 或 m 为 0 时,结束输入。
  • 地图读取:使用嵌套的 for 循环读取地图的每一个字符,并存储在 map 数组中。
  • 油田计数:初始化油田数量 sum 为 0。再次使用嵌套的 for 循环遍历地图的每个位置,如果遇到 @ 字符,则调用 dfs 函数将该油田的所有 @ 字符标记为已访问,并将油田数量 sum 加 1。
  • 输出结果:输出地图中油田的总数。

总结

该代码通过深度优先搜索算法,从每个未访问的 @ 字符开始,递归地标记所有相连的 @ 字符,从而实现对油田的计数。最终输出地图中油田的总数。

代码


#include<iostream>
using namespace std;
int dx[9]={0,-1,-1,0,1,1,1,0,-1};
int dy[9]={0,0,1,1,1,0,-1,-1,-1};
char map[105][105];
int n,m;
void dfs(int x,int y){map[x][y]='*';for(int i=0;i<9;i++){if(dx[i]==0 && dy[i]==0) continue;int mx=x+dx[i];int my=y+dy[i];if(mx>=0 && mx<n && my>=0 && my<m && map[mx][my]=='@'){dfs(mx,my);}}
}
int main(){int sum;while(cin>>n>>m){if(n==0 || m==0) break;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>map[i][j];}}sum=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(map[i][j]=='@'){dfs(i,j);sum++;}}}cout<<sum<<endl;}return 0;
}

http://www.xdnf.cn/news/181351.html

相关文章:

  • 【数据可视化-39】2009-2019年亚马逊50大畅销书数据集可视化分析
  • 迷你世界UGC3.0脚本Wiki世界模块管理接口 World
  • Mysql中隐式内连接和显式内连接的区别
  • (26)VTK C++开发示例 ---将点坐标写入PLY文件
  • linux:进程的替换
  • 大模型时代具身智能:从理论突破到产业落地的全链路解析
  • 自动伴随无人机说明文档
  • Netmiko 源码关键流程图
  • pytorch学习使用
  • 深入解析MyBatis-Plus中的lambdaUpdate与lambdaQuery
  • OpenCV 图形API(65)图像结构分析和形状描述符------拟合二维点集的直线函数 fitLine2D()
  • 文章记单词 | 第47篇(六级)
  • java map中的key区分大小写吗
  • ChatGPT与DeepSeek在科研论文撰写中的整体科研流程与案例解析
  • 【git】添加项目到已有gitee仓库
  • vue组件间通信
  • 蓝桥杯 9.生命之树
  • 【Multipath】dm软链接相关问题定位
  • 前端高频面试题day3
  • Python装饰器:函数增强的秘密武器
  • 使用ZXing开发安卓扫码功能
  • 【C++】C++11新特性(一)
  • 【前端】element表格X轴滚动优化拖拽滚动
  • 函数式编程之 Optional
  • 海底世界-第16届蓝桥第4次STEMA测评Scratch真题第5题
  • 【jax】ms(毫秒)和 μs(微秒)
  • Leetcode395.至少有 K 个重复字符的最长子串
  • Qt从零开始(1)了解
  • Golang | 倒排索引Value的设计
  • Python爬虫实战:获取ya马逊最新销售飙升榜数据并做分析,为电商选品做参考