两句话

用户名：uq_42709742140

访问量：3392

签　名：

等　　级
排　　名	2787
经　　验	2149
参赛次数	0
文章发表	37
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Seq2Seq的学习总结
浏览：50

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

递归 + DFS 练习记录（三）

　　作者: 两句话　　　　发表时间：2024-04-04 21:55:07 浏览：46　|　评论：0　

##P1683 入门
**链接：**https://www.luogu.com.cn/problem/P1683

**思路：**
string[N]型变量存放迷宫，遍历，当找到开始字符的时候开始搜索。按照四连通方向寻找路径，不能超出范围，不能重复走过，不能走不可走的石头，都满足条件之后从下一位可以走的路径继续进行搜素。

**注意：**
注意只能走一次，不能回溯否则会循环，走完之后标准置为true。
```cpp
#include<iostream>
using namespace std;

const int N = 30;

int n , m , res = 0;
char g[N][N];
bool st[N][N];

int dx[] = {-1 ,0 ,1 ,0};   //方向数组
int dy[] = {0 ,1 ,0 ,-1};

void dfs(int x, int y)
{
    for(int i = 0;i < 4;i ++)
    {
        int a = x + dx[i] , b = y + dy[i];
        // cout<<a<<' '<<b<<endl;
        
        if(a < 0 || a >= n || b < 0 || b >= m)    continue;
        if(g[a][b] != '.')  continue;   //如果不是安全的石头则不能通过
        if(st[a][b])    continue;   //如果当前石头已经走过则不能再走
        
        st[a][b] = true;    //避开以上所有条件，选择走当前的石头
        res ++;
        dfs(a , b);     //从当前石头开始继续搜索
    }
}

int main()
{
    scanf("%d%d" , &m , &n);
    for(int i = 0;i < n;i ++)
        scanf("%s" , g[i]);     //输入一行
        
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < m;j ++)
            if(g[i][j] == '@')  
            {
                st[i][j] = true;
                dfs(i , j);
            }
    
    res ++;
    printf("%d\n" , res);
    return 0;
}
```
##P1596 Lake Counting S
**链接：**https://www.luogu.com.cn/problem/P1596

**思路：**
思路与上题很相似。

**注意：**
注意是八连通区域（写法），不能回溯否则会循环，走完之后标准置为true。
```cpp
#include<iostream>
using namespace std;

const int N = 110;
char g[N][N];
bool st[N][N];
int n , m ,res = 0;

int dx[] = {1 ,1 ,1 ,0 ,0 ,-1 ,-1 ,-1};
int dy[] = {0 ,1 ,-1 ,1 ,-1 ,0 ,1 ,-1};

void dfs(int x , int y)
{
    for(int i = 0;i < 8;i ++)
    {
        int a = x + dx[i] , b = y + dy[i];

//注意a的范围是n，b的范围是【m】!，别弄混
        if(a < 0 || a >= n || b < 0 ||b >= m)  continue;
        if(g[a][b] != 'W')  continue;
        if(st[a][b])  continue;

st[a][b] = true;
        dfs(a , b);
    }
}

int main()
{
    scanf("%d%d" , &n ,&m);
    for(int i = 0;i < n;i ++)
        scanf("%s" , g[i]);

for(int i = 0;i < n;i ++)
        for(int j = 0;j < m;j ++)
            if(g[i][j] == 'W' && !st[i][j])
            {
                dfs(i , j);
                res ++;
            }

printf("%d\n" , res);
    return 0;
}
```
##P1025 [NOIP2001 提高组] 数的划分
**链接：**https://www.luogu.com.cn/problem/P1025

**思路：**
组合问题。i = start，从第一个位置开始试探，如果可以就将当前数字i放在当前位置x，接着判断下一个位置上的数字，数字可以有一个重复，故下一位从i开始试探。和为目标数字时，找到一个解

**注意：**
开始时i = start ， 循环过程中i <= n - nowsum（剪枝的一种，无效的i不用过多试探）。
```cpp
#include<iostream>
using namespace std;

const int N = 10010;
int n , k;
int arr[N];
int res = 0;

void dfs(int x , int start , int nowsum)
{
    if(x > k)
    {
        if(nowsum == n)
        {
            // for(int i = 1;i <= k;i ++)
            //     printf("%3d" , arr[i]);
            // puts("");  
            res ++;
        }
        return ;
    }
    
    for(int i = start;i <= n - nowsum;i ++)
    {//要注意i的循环范围，加上综合比n大时可以直接跳出
        arr[x] = i;
        dfs(x + 1 , i , nowsum + i);
        arr[x] = 0;
    }
}

int main()
{
    scanf("%d%d" , &n , &k);
    dfs(1 , 1 , 0);
    printf("%d\n" , res);
    
    return 0;
}
```
##1114. 棋盘问题
**链接：**https://www.acwing.com/problem/content/1116/

**思路：**
开一个列状态数组，如果如果当列没有放过，并且该位置满足条件，则该位置可以放置，第一个参数记录行，第二个参数记录放置棋子数。要回溯，放置之后置为true。

**注意：**
本题中存在棋子数小于列数的情况，当棋子数小于列数时，要强制进行下一轮搜索dfs(x + 1 , cnt);放最后。
```cpp
#include<iostream>
using namespace std;

const int N = 10;
int n , k;
char g[N][N];
bool st[N];
int res = 0;

void dfs(int x , int cnt)
{
    if(cnt == k){
        res ++; //找到一个结果
        return ;
    }

if(x >= n) return;  //剪枝

for(int i = 0;i < n;i ++)
    {
        if(!st[i] && g[x][i] == '#')
        {//如果当列没有放过，该位置可以放置
            st[i] = true;
            dfs(x + 1, cnt + 1);
            st[i] = false;
        }
    }

dfs(x + 1 , cnt);   //当棋子数小于列数时，强制进行下一轮搜索
}

int main()
{
    while(cin>>n>>k , n > 0 && k > 0)
    {
        for(int i = 0;i < n;i ++)   scanf("%s" , g[i]);

res = 0;
        dfs(0 , 0);
        printf("%d\n" , res);
    }
    return 0;
}
```
##P1019 [NOIP2000 提高组] 单词接龙
**链接：**https://www.luogu.com.cn/problem/P1019

**思路：**
substr（），开一个二维数组用于存放不同的串之间的接龙情况（首尾重复字符）。

**注意：**
substr(起始位置，长度)，取子字符串。
```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 30;

int n , res = 0;
int used[N];    //用过的次数
int g[N][N];    //单词重复个数
string word[N]; //单词存储

void dfs(string d , int x)
{//龙头，当前单词
    res = max(res , (int)d.size()); //查找当前单词的最大长度

used[x]++;
    for(int i = 0;i < n;i ++)
    {//如果当前两个单词有重复部分且i用的少于2次
        if(g[x][i] && used[i] < 2)  dfs(d + word[i].substr(g[x][i]) , i);
    }
    used[x] --; //回溯
}

int main()
{
    scanf("%d" , &n);
    for(int i = 0;i < n;i ++)
        cin>>word[i];
        
    char start;
    cin>>start;
    
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < n;j ++)
        {//substr(起始位置，长度)，取子字符串
            string a = word[i] , b = word[j];
            for(int k = 1;k < min(a.size() , b.size());k ++)
                if(a.substr(a.size() - k , k) == b.substr(0 , k))
                {
                    g[i][j] = k;
                    break;
                }
        }
        
    for(int i = 0;i < n;i ++)
        if(word[i][0] == start) dfs(word[i] , i);
        
    printf("%d\n" , res);
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

两句话

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）看不懂的点我

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

三进制小数（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

递归 + DFS 练习记录（三）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

C语言考试练习题_排列（C++代码）

C语言训练-字符串正反连接（C语言代码）

简单的a+b （C语言代码）

剔除相关数（C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

程序员的表白（C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

两句话

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）看不懂的点我

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

三进制小数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

递归 + DFS 练习记录（三）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

C语言考试练习题_排列 （C++代码）

C语言训练-字符串正反连接 （C语言代码）

简单的a+b （C语言代码）

剔除相关数 （C语言代码）

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

程序员的表白 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

汽水瓶（C语言代码）看不懂的点我

三进制小数（C语言代码）

　　评论区

C语言考试练习题_排列（C++代码）

C语言训练-字符串正反连接（C语言代码）

剔除相关数（C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

程序员的表白（C语言代码）