【洛谷】P1443、B3625题解
【洛谷】P1443、B3625题解
@VON
发布于 2025-12-21 09:22:59
发布于 2025-12-21 09:22:59
P1443
题目
思路
一个简单的深搜题，只需要记录走到各各位置的步数即可
豆包解释
这段代码的核心思路是使用广度优先搜索（BFS）算法来计算在一个二维网格中，从给定的起始点 (x, y) 出发，马按照 “日” 字形走法到达网格中每个可达点所需的最少步数。下面为你详细分析代码的具体思路：
整体流程
- 输入处理：在
main函数中，首先读取网格的行数n、列数m以及起始点的坐标(x, y)。 - 广度优先搜索：调用
bfs函数，从起始点开始进行广度优先搜索，计算到达每个可达点的最少步数。 - 结果输出：调用
print_arr函数，输出记录每个点最少步数的二维数组val。
代码各部分详细思路
全局变量和常量
cpp
int n, m, x, y;
int val[420][420];
int dxy[8][2] = {{2, 1}, {-2, 1}, {1, 2}, {1, -2}, {2, -1}, {-2, -1}, {-1, 2}, {-1, -2}};n和m分别表示网格的行数和列数。x和y表示起始点的坐标。val数组用于记录从起始点到每个点的最少步数，初始值为-1表示该点尚未被访问。dxy数组存储了马的八个可能的移动方向，每个方向用一个二维向量表示。
初始化函数 init
void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
val[i][j] = -1;
}
}
}- 该函数的作用是将
val数组的所有元素初始化为-1，表示所有点都尚未被访问。
打印函数 print_arr
void print_arr() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << val[i][j] << " ";
}
cout << endl;
}
}- 该函数用于打印
val数组，输出从起始点到每个点的最少步数。
坐标检查函数 check
bool check(int x, int y) {
if (x < 1 || x > n || y < 1 || y > m) return false;
return true;
}- 该函数用于检查给定的坐标
(x, y)是否在网格范围内，如果在范围内则返回true，否则返回false。
节点结构体 node
struct node {
int x, y;
int step;
};- 该结构体用于表示一个节点，包含节点的坐标
(x, y)以及从起始点到该节点的步数step。
广度优先搜索函数 bfs
void bfs(int x, int y) {
init();
queue<node> ans;
node p;
p.x = x, p.y = y, p.step = 0;
ans.push(p);
val[x][y] = 0;
while (!ans.empty()) {
node cur = ans.front();
ans.pop();
for (int i = 0; i < 8; i++) {
int mx = cur.x + dxy[i][0];
int my = cur.y + dxy[i][1];
if (check(mx, my) && val[mx][my] == -1) {
node temp;
temp.x = mx, temp.y = my, temp.step = cur.step + 1;
val[mx][my] = temp.step;
ans.push(temp);
}
}
}
}- 初始化
val数组，将所有元素初始化为-1。 - 创建一个队列
ans，用于存储待访问的节点。 - 将起始节点
p加入队列，并将起始点的步数设置为 0。 - 进入循环，当队列不为空时，取出队首节点
cur。 - 遍历马的八个可能的移动方向，计算新的坐标
(mx, my)。 - 检查新坐标是否在网格范围内且尚未被访问，如果是，则创建新节点
temp，更新其步数为当前节点的步数加 1，将新节点加入队列，并更新val数组中该点的步数。
主函数 main
int main() {
cin >> n >> m >> x >> y;
bfs(x, y);
print_arr();
return 0;
}- 读取输入的网格行数
n、列数m以及起始点的坐标(x, y)。 - 调用
bfs函数进行广度优先搜索。 - 调用
print_arr函数输果。
AC代码
#include<iostream>
#include<queue>
using namespace std;
int n,m,x,y;
int val[420][420];
//int dxy[4][2]= {{0,1},{0,-1},{-1,0},{1,0}};//四个方向
//int dxy[8][2]= {{-1,0},{0,-1},{1,0},{0,1},{1,1},{-1,1},{-1,-1},{1,-1}};//八个方向
int dxy[8][2]= {{2,1},{-2,1},{1,2},{1,-2},{2,-1},{-2,-1},{-1,2},{-1,-2}};//马的八个方向
//int dxy[6][3]= {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};//三维方向
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
val[i][j]=-1;
}
}
}
void print_arr(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<val[i][j]<<" ";
}
cout<<endl;
}
}
bool check(int x,int y){
if(x<1 || x>n || y<1 ||y>m) return false;
return true;
}
struct node{
int x,y;
int step;
};
void bfs(int x,int y){
init();
queue<node>ans;
node p;
p.x=x,p.y=y,p.step=0;
ans.push(p);
val[x][y]=0;
while(!ans.empty()){
node cur=ans.front();
ans.pop();
for(int i=0;i<8;i++){
int mx=cur.x+dxy[i][0];
int my=cur.y+dxy[i][1];
if(check(mx,my) && val[mx][my]==-1){
node temp;
temp.x=mx,temp.y=my,temp.step=cur.step+1;
val[mx][my]=temp.step;
ans.push(temp);
}
}
}
}
int main(){
cin>>n>>m>>x>>y;
bfs(x,y);
print_arr();
return 0;
}B3625
题目
思路
本题没有让输出路径，简单了一个级别，也是基础的搜索题，检查是否可以通行 到终点结束while循环即可
豆包解释
这段代码的核心思路是运用广度优先搜索（BFS）算法来判定在一个二维地图里，是否能够从起点 (1, 1) 抵达终点 (n, m)。以下是对代码详细的思路分析：
整体流程
- 输入处理：在
main函数中，先读取地图的行数n和列数m，接着逐行读取地图的具体布局并存储在map数组中。 - 广度优先搜索：调用
bfs函数，从起点(1, 1)开始进行广度优先搜索，判断是否可以到达终点。 - 结果输出：依据
bfs函数的返回值，输出相应的结果（Yes或者No）。
代码各部分详细思路
全局变量和常量
int n, m;
struct node{
int x, y;
};
int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
char map[105][105];
int val[105][105];
queue<node> ans;n和m分别代表地图的行数和列数。node结构体用来表示地图上的一个点，包含该点的横坐标x和纵坐标y。dxy数组存储了四个方向（上、右、下、左）的偏移量，用于在搜索时确定相邻的点。map数组用于存储地图的布局，其中.表示通路，其他字符可视为障碍物。val数组用于标记某个点是否已经被访问过，0表示未访问，1表示已访问。ans是一个队列，用于存储待访问的点。
广度优先搜索函数 bfs
bool bfs(int x, int y) {
node p; // 起点
p.x = x;
p.y = y;
val[x][y] = 1;
ans.push(p);
while (!ans.empty()) {
node cur = ans.front();
ans.pop();
if (cur.x == n && cur.y == m && map[n][m] == '.') {
return true;
}
for (int i = 0; i < 4; i++) {
int mx = cur.x + dxy[i][0];
int my = cur.y + dxy[i][1];
if (map[mx][my] == '.' && val[mx][my] == 0) {
val[mx][my] = 1;
node temp;
temp.x = mx;
temp.y = my;
ans.push(temp);
}
}
}
return false;
}- 初始化起点
p，并将其标记为已访问（val[x][y] = 1），然后把起点加入队列ans。 - 进入循环，只要队列不为空，就取出队首元素
cur。 - 检查当前点
cur是否为终点，若为终点且终点是通路（map[n][m] == '.'），则返回true，表示可以到达终点。 - 遍历四个方向，计算相邻点的坐标
(mx, my)。 - 检查相邻点是否为通路且未被访问过，若满足条件，则将该点标记为已访问，并加入队列
ans。 - 若队列为空仍未找到终点，则返回
false，表示无法到达终点。
主函数 main
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> map[i][j];
}
}
if (bfs(1, 1)) cout << "Yes";
else cout << "No";
return 0;
}- 读取地图的行数
n和列数m，并逐行读取地图的布局。 - 调用
bfs函数，从起点(1, 1)开始搜索。 - 根据
bfs函数的返回值，输出Yes或No。
AC代码
#include<iostream>
#include<queue>
using namespace std;
int n,m;
struct node{
int x,y;
};
int dxy[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
char map[105][105];
int val[105][105];
queue<node> ans;
bool bfs(int x,int y){
node p;//起点
p.x=x;
p.y=y;
val[x][y]=1;
ans.push(p);
while(!ans.empty()){
node cur = ans.front();
ans.pop();
if(cur.x==n && cur.y==m && map[n][m]=='.'){
return true;
}
for(int i=0;i<4;i++){
int mx=cur.x+dxy[i][0];
int my=cur.y+dxy[i][1];
if(map[mx][my]=='.' && val[mx][my]==0){
val[mx][my]=1;
node temp;
temp.x=mx,temp.y=my;
ans.push(temp);
}
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>map[i][j];
}
}
if(bfs(1,1)) cout<<"Yes";
else cout<<"No";
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号