设计师个人网站欣赏,大连建设工程信息网官网首页,网站优化技巧,宁波网站建设果核P1605 迷宫 前言题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题目分析注意事项 代码后话王婆卖瓜 题目来源 前言
没什么好说的深搜yyds#xff01;直接深搜一遍过#xff01;
题目
题目描述
给定一个 N M N \times M NM 方格的迷宫#xff0c;迷… P1605 迷宫 前言题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题目分析注意事项 代码后话王婆卖瓜 题目来源 前言
没什么好说的深搜yyds直接深搜一遍过
题目
题目描述
给定一个 N × M N \times M N×M 方格的迷宫迷宫里有 T T T 处障碍障碍处不可通过。
在迷宫中移动有上下左右四种方式每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标每个方格最多经过一次问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 N , M , T N,M,T N,M,T分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY S X , S Y SX,SY SX,SY 代表起点坐标 F X , F Y FX,FY FX,FY 代表终点坐标。
接下来 T T T 行每行两个正整数表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
样例 #1
样例输入 #1
2 2 1
1 1 2 2
1 2样例输出 #1
1提示
对于 100 % 100\% 100% 的数据 1 ≤ N , M ≤ 5 1 \le N,M \le 5 1≤N,M≤5 1 ≤ T ≤ 10 1 \le T \le 10 1≤T≤10 1 ≤ S X , F X ≤ n 1 \le SX,FX \le n 1≤SX,FX≤n 1 ≤ S Y , F Y ≤ m 1 \le SY,FY \le m 1≤SY,FY≤m。
题目分析 这道题就是典型的搜索虽然加了一个障碍但是其实没啥影响顶多多一个if就完了这边虽然我已经理解了但还是给大家讲一下深搜的思路以本题为例 首先深搜是递归的你要先传入一个值作为首次的参数这个一般都是起始点和0或者1这样。dfs(sx,sy); 然后就是一个判断这个判断需要放在整个dfs的最前面来判断是否到了终止条件比如无路可走到达终点或者说是完成目标相当于递归的终点。这个判断不准确也是导致dfs死循环的重要原因之一。 if(xfxyfy) {total;return;}接着就是主体部分根据本层dfs传来的参数将遍历所有可能的情况上下左右寻找可行点一般还会加上边界访问判断没有设置已访问也容易导致死循环等这题还需要判断陷阱不过跟前面合在一起了。然后遇到可行点就标记访问进入下一层也就是新的点的dfs退出来时再恢复一下现场还原为未访问。 map[newx][newy]1;//标记为已访问dfs(newx,newy);map[newx][newy]0;//恢复现场 注意事项
1.记得起始点也要标记为访问过否则会多几条路。 2.陷阱在这里判断跟判断访问差不多 3.记得恢复现场
代码
一遍过说实话还是挺喜欢做这种搜索的深搜yyds! #includeiostreamusing namespace std;int n,m,t,sx,sy,fx,fy,a,b,total0;
int map[500][500] {0};
int dx[4] {1,0,-1,0};
int dy[4] {0,-1,0,1};
struct point {int x,y;
} trap[12];
void dfs(int x,int y)
{if(xfxyfy) {total;return;}for(int i0; i4; i) {int newxxdx[i],newyydy[i];if(newx1newxnnewy1newym) if(map[newx][newy]0)//包括不是陷阱以及没有访问过 {map[newx][newy]1;//标记为已访问dfs(newx,newy);map[newx][newy]0;//恢复现场 }}
}
int main()
{cinnmt;cinsxsyfxfy;for(int i0; it; i) {cinab;map[a][b]-1;//表示陷阱}map[sx][sy]1;dfs(sx,sy);couttotalendl;return 0;
}
后话
王婆卖瓜
感觉有收获或者想跟上我的进度刷题的可以点个关注或者点赞收藏评论都可以
题目来源 USACO 洛谷链接
