U5-2-DFS-2
原题链接：67324.4.0U5笔记合集
2025-08-31 11:22:26
发布于：江苏
15阅读
0回复
0点赞
一、上节课作业+课堂案例
1.抽奖5
#include <iostream>
using namespace std;
int a[105], n, b[105];
bool vis[105];
void dfs(int k)
{
if (k > n){
for (int i=1; i<=n; i++) cout<<b[i]<<' ';
cout<<endl;
return ;
}
for (int i=1; i<=n; i++) {
if (vis[i] == 0) {
b[k] = a[i];
vis[i] = 1;
dfs(k+1);
vis[i] = 0; //回溯
}
}
}
int main()
{
cin >> n;
for (int i=1; i<=n; i++) cin>>a[i];
dfs(1);
return 0;
}
2.抽奖6-1
//TLE 第3个点
#include <bits/stdc++.h>
using namespace std;
int a[105], n, m, b[105], ans;
bool vis[105];
bool prime(int x){
if (x<2) return 0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0) return 0;
return 1;
}
void dfs(int k)
{
if (k > m){
int sum = 0;
for (int i=1; i<=m; i++) {
sum += b[i];
}
if (prime(sum)) {
ans++;
// for (int i=1; i<=m; i++) cout<< b[i]<<' ';
// cout<<endl;
}
return ;
}
for (int i=1; i<=n; i++) {
if (vis[i] == 0) {
b[k] = a[i];
vis[i] = 1;
dfs(k+1);
vis[i] = 0; //回溯
}
}
}
int fac(int y){
int ret = 1;
for (int i=1; i<=y; i++) ret *= i;
return ret;
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) cin>>a[i]; //积分
dfs(1);
cout << ans/fac(m);
return 0;
}
/*
4 3
3 7 12 19
*/
3.抽奖6-2
#include <bits/stdc++.h>
using namespace std;
int a[105], n, m, b[105], ans;
bool prime(int x)
{
if (x<2) return 0;
for (int i=2; i<=sqrt(x); i++)
if (x%i==0) return 0;
return 1;
}
//从st位置开始抽, 第k次抽奖
void dfs(int st, int k)
{
if (k == m+1) {
int sum = 0;
for (int i=1; i<=m; i++) {
sum += b[i];
}
if (prime(sum)) {
ans++;
}
return ;
}
//从st~n的区间内开始抽
for (int i=st; i<=n; i++) {
b[k] = a[i];
dfs(i+1, k+1);
}
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) cin>>a[i]; //积分
dfs(1, 1);
cout << ans;
return 0;
}
/*
4 3
3 7 12 19
*/
4.迷宫的入口判断
#include <iostream>
using namespace std;
int mp[105][105];
int n, m, flag;
bool vis[105][105];
int dir[4][2] = {1,0, -1, 0, 0, -1, 0, 1};
void dfs(int x, int y)
{
if (x==n && y==m) { //1.递归出口
flag = 1;
return ;
}
for (int i=0; i<4; i++) { //2. 开始朝四个方向进行搜索
int a = x + dir[i][0];
int b = y + dir[i][1];
if (a<1 || b<1 || a>n || b>m) continue; //越界
if (vis[a][b] || mp[a][b]==1) continue; //已访问 || 障碍物
vis[a][b] = 1;
dfs(a, b);
}
}
int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin >> mp[i][j];
}
}
dfs(1, 1); //从1,1这个点开始搜索
if (flag) cout<<"YES";
else cout << "NO";
return 0;
}
5.迷宫方案数
#include <iostream>
using namespace std;
int n, m, sx, sy, fx, fy, t, cnt;
int mp[105][105];
int dir[4][2] = {1,0,0,1,0,-1,-1,0};
bool vis[105][105];
void dfs(int x, int y)
{
if (x==fx && y==fy) {
cnt++;
return ;
}
for (int i=0; i<4; i++) {
int a = x+dir[i][0], b = y+dir[i][1];
if (a<1 || b<1 || a>n || b>m) continue;
if (mp[a][b] == 1 || vis[a][b] == 1) continue;
vis[a][b] = 1;
dfs(a, b);
vis[a][b] = 0; //回溯
}
}
int main()
{
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
while (t--) {
int x, y;
cin >> x >> y;
mp[x][y] = 1;
}
vis[sx][sy] = 1;
dfs(sx, sy);
cout << cnt;
return 0;
}
/*
2 2 1
1 1 2 2
1 2
*/
6.迷宫最短路径(消灭怪兽)
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {-1,0,1,0,0,-1,0,1};
int n, m, t, sx, sy, fx, fy;
int ans = 1e9;
char mp[105][105];
bool vis[105][105];
void dfs(int x, int y, int times){
if (mp[x][y] == 'W'){
ans = min(ans, times); //更新最短时间
return ;
}
for(int i=0; i<4; i++){
int a = x + dir[i][0];
int b = y + dir[i][1];
if (a<1 || a>n || b<1 || b>m) continue;
if (mp[a][b] == '#' || vis[a][b]) continue;
vis[a][b] = 1;
if (mp[a][b]>='1' && mp[a][b] <='9') //加上消灭怪兽的时间
dfs(a, b, times + 1+(mp[a][b]-48));
else
dfs(a, b, times+1);
vis[a][b] = 0; //回溯
}
}
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> mp[i][j];
if (mp[i][j] == 'Z'){
sx = i;
sy = j;
}
}
}
vis[sx][sy] = 1; //第一个点也要标记
dfs(sx, sy, 0);
if (ans == 1e9) cout << "IMPOSSIBLE";
else cout << ans;
return 0;
}
二、作业
1. 走迷宫
/*
[走迷宫]
题目描述
有一个 m×n 格的迷宫(表示有 m 行、n 列)，其中有可走的也有不可走的，
如果用 1 表示可以走，0 表示不可以走，文件读入这 m×n 个数据和起始点、结束点
（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。
现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。
如果一条路都不可行，则输出相应信息（用 -1 表示无路）。
优先顺序：左上右下。数据保证随机生成。
输入格式
第一行是两个数 m,n(1<m,n<15)，
接下来是 m 行 n 列由 1 和 0 组成的数据，最后两行是起始点和结束点。
输出格式
所有可行的路径，描述一个点时用 (x,y) 的形式，除开始点外，其他的都要用 -> 表示方向。
如果没有一条可行的路则输出 -1。
样例组
输入#1
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
输出#1
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
*/
/*
注意这题的方向数组是固定的，题目对方向有要求，另外就是有标记的一直dfs, 过程中需要用数组记录一下轨迹
难点在 dfs后的轨迹步数需要回退一步，同回溯
*/
#include<bits/stdc++.h>
using namespace std;
int mp[20][20];
int vis[20][20];
int dir[4][2] = {
{0,-1},{-1,0},{0,1},{1,0}
};
//st:start起点 ed:end终点
int stx,sty;
int edx,edy;
int path[400][2]; //记录路径,第一维表示顺序，第二维表示位置
int pathsize; //当前记录的路径长度
int n,m;
int flag; //记录是否存在至少一条路径
bool in(int x,int y) { //判断是否在迷宫内
return x > 0 && x <= n && y > 0 && y <= m;
}
void dfs(int x,int y) {
if((x == edx) && (y == edy)) {
flag = 1;
cout << "(" << stx << "," << sty << ")"; //总首先输出起点
for(int i = 0; i < pathsize; i++)
cout << "->(" << path[i][0] << "," << path[i][1] << ")";
cout << endl;
return;
}
for(int i = 0; i < 4; i++) {
int tmpx = x + dir[i][0];
int tmpy = y + dir[i][1];
if(in(tmpx,tmpy) && mp[tmpx][tmpy] == 1 && (!vis[tmpx][tmpy])) {
//只有满足在区域内，是1，没被访问过才能继续dfs
vis[tmpx][tmpy] = 1;
path[pathsize][0] = tmpx; //记录坐标
path[pathsize++][1] = tmpy;
dfs(tmpx,tmpy);
pathsize--;
vis[tmpx][tmpy] = 0;
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> mp[i][j];
cin >> stx >> sty;
cin >> edx >> edy;
vis[stx][sty] = 1;
dfs(stx, sty);
if(!flag) cout << "-1";
}
2. 入门
/*
思路，其实这题就是一直dfs，走到走不下去就是最多的步数了
*/
#include <iostream>
using namespace std;
const int N = 30;
int w, h, sx, sy, sum;
char mp[N][N];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
bool vis[N][N]; //vis[x][y] 标记点(x,y)是否已访问
bool check(int x, int y) {
return x >= 1 && x <= h && y >= 1 && y <= w;
}
void dfs(int x, int y) { //当前正在访问的点是(x,y)
vis[x][y] = true; //标记点(x,y)已访问
for(int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(check(nx, ny) && !vis[nx][ny] && mp[nx][ny] == '.') {
sum++;
dfs(nx,ny); //递归访问点(nx,ny)
}
}
return;
}
int main() {
cin >> w >> h; //先输入列数，再输入行数
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
cin >> mp[i][j];
if(mp[i][j] == '@') {
sx = i;
sy = j;
}
}
}
sum++;
dfs(sx,sy);
cout << sum;
return 0;
}
/*
[入门]
题目描述
不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。
所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。
有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，
那你就死翘翘了，我们认为是不安全的。
你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。
由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，
并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），
现在她告诉你进入桃花岛的秘密就是：
如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。
注意：瓷砖可以重复走过，但不能重复计数。
提示
对于全部的测试点，保证 1≤W,H≤20。
输入格式
第一行两个正整数 W 和 H，分别表示小路的宽度和长度。
以下 H 行为一个 H×W 的字符矩阵。每一个字符代表一块瓷砖。
其中，. 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。
输出格式
输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。
样例组
输入#1
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
输出#1
59
*/
这里空空如也
有帮助，赞一个