关于DFS几道比较基础的题_dfs基础题

1. 题目一 FatMouse and Cheese
   题目大意就是说有一个老鼠在N*N的网格当中每一步最多只能走K格 并且由于猫的存在每一次老鼠的移动都必须比路径上一个网格收集的奶酪多 问这条路径上老鼠收集的奶酪最大值

Sample Input
3 1
1 2 5
10 11 6
12 12 7
-1 -1
Sample Output
37
1
2
3
4
5
6
7
8

PS： 终点的位置不是固定的 满足上下左右都不存在比当前更大的网格的条件 即四周都比当前网格值小

#include<bits/stdc++.h>
using namespace std;

const int maxn=105;
int n,k,nx,ny;
int vis[maxn][maxn],dp[maxn][maxn];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int dfs(int x,int y)
{
    int i,j,nx,ny,ans=0;
    if(dp[x][y])
        return dp[x][y];//联系到第二个return 即已经进行赋值表示找到了最大路径
    for(i=0;i<4;i++)
    {
        for(j=1;j<=k;j++)
        {
            nx=x+j*dx[i];//每次移动1~k个网格
            ny=y+j*dy[i];
            if(nx>0&&nx<=n&&ny>0&&ny<=n&&vis[nx][ny]>vis[x][y])
            {
                ans=max(ans,dfs(nx,ny));//一直往(nx,ny)的方向递归找最大路径
            }
        }
    }
    return dp[x][y]=ans+vis[x][y];//已经走到了终点加上终点的值
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==-1&&k==-1)
            break;
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%d",&vis[i][j]);
        printf("%d\n",dfs(1,1));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2. 题目二 字符的全排列问题 有n个字符 请你输出该n个字符的全排列

Sample Input
1
abc
Sample Output
a b c
a c b
b a c
b c a
c a b
c b a
1
2
3
4
5
6
7
8
9
10

#include<stdio.h>
#include<string.h>

int n;
char  a[15];
char re[15];
int vis[15];
void dfs(int step)
{
    int i;
    if(step==n+1)//判断边界
    {
        for(i=1;i<=n;i++)
      
1
2
3
4
5
6
7
8
9
10
11
12
13