迷宫(dfs)

一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 n∗n 的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#),则看成无法办到。

注意:A、B不一定是两个不同的点。

输入格式
第1行是测试数据的组数 k,后面跟着 k 组输入。

每组测试数据的第1行是一个正整数 n,表示迷宫的规模是 n∗n 的。

接下来是一个 n∗n 的矩阵,矩阵中的元素为.或者#。

再接下来一行是 4 个整数 ha,la,hb,lb,描述 A 处在第 ha 行, 第 la 列,B 处在第 hb 行, 第 lb 列。

注意到 ha,la,hb,lb 全部是从 0 开始计数的。

输出格式
k行,每行输出对应一个输入。

能办到则输出“YES”,否则输出“NO”。

数据范围
1≤n≤100
输入样例:
2
3
.##
…#
#…
0 0 2 2
5

###.#
…#…
###…
…#.
0 0 4 0
输出样例:
YES
NO

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 899;
char a[N][N];
bool v[N][N];
int n,m,x1,y1,x2,y2;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};

bool dfs(int x,int y)
{
    if(a[x][y]=='#') return false;
    if(x==x2&&y==y2) return true;
    v[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=n) continue;
        if(v[a][b]) continue;
        
        if(dfs(a,b)) return true;
    }
    return false;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(v,0,sizeof(v));	//因为有多组数据,记得清零
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
            }
        }
        cin>>x1>>y1>>x2>>y2;
        
        if(dfs(x1,y1)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

红与黑(dfs,求连通块面积)

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。

请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下

1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时,表示输入结束。

输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围
1≤W,H≤20
输入样例:
6 9
…#.
…#





#@…#
.#…#.
0 0
输出样例:
45

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000;
char a[N][N];
int v[N][N],n,m,x,y;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int ans=0;

void dfs(int x,int y)
{
    v[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int aa=x+dx[i],bb=y+dy[i];
        if(aa<0||aa>=n||bb<0||bb>=m) continue;
        if(v[aa][bb]) continue;
        if(a[aa][bb]!='.') continue;
        dfs(aa,bb);
        ans++;   
    }
}

int main()
{
    while(cin>>m>>n,m||n)
    {
        memset(v,0,sizeof(v));	//多组数据
        ans=1;		//出发点自己也算一个瓷砖
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>a[i][j];
            }
        }
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(a[i][j]=='@')
                {
                    x=i;
                    y=j;
                }
            }
        }
        dfs(x,y);
        cout<<ans<<endl;
    } 
}

马走日(dfs回溯)

马在中国象棋以日字形规则移动。

请编写一段程序,给定 n∗m 大小的棋盘,以及马的初始位置 (x,y),要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点。

输入格式
第一行为整数 T,表示测试数据组数。

每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标 n,m,x,y。

输出格式
每组测试数据包含一行,为一个整数,表示马能遍历棋盘的途径总数,若无法遍历棋盘上的所有点则输出 0。

数据范围
1≤T≤9,
1≤m,n≤9,
0≤x≤n−1,
0≤y≤m−1
输入样例:
1
5 4 0 0
输出样例:
32

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 11;
int v[N][N],n,m,t;
int ans,step;
int dx[]={1,2,2,1,-1,-2,-2,-1},dy[]={2,1,-1,-2,-2,-1,1,2};

void dfs(int x,int y,int step)
{
    if(step==n*m) 
    {
        ans++;
        return;
    }
    
    v[x][y]=true;
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=m) continue;
        if(v[a][b]) continue;
        
        dfs(a,b,step+1);
        v[a][b]=false;
        
    }
}

int main()
{
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>n>>m>>x>>y;
        memset(v,0,sizeof(v));
        ans=0;
        dfs(x,y,1);
        cout<<ans<<endl;
    }
}

##111. 二叉树的最小深度

dfs:

class Solution {
public:
    int ans=0;
    int minDepth(TreeNode* root) {
        if(root==nullptr) return 0;

        int left=minDepth(root->left);  //计算左子树深度
        int right=minDepth(root->right);    //计算右子树深度

        if(left!=0&&right!=0) return min(left,right)+1; //如果都存在则不是叶子结点,深度为最小值+1
        return left+right+1;    //否则为存在的那个节点深度+1
    }   
};

bfs:

class Solution {
public:
    int ans=0;
    queue<pair<TreeNode*,int>> q;

    int minDepth(TreeNode* root) {  
        if(root==nullptr) return 0;     
        return bfs(root);
    }

    int bfs(TreeNode*root)
    {
        q.push({root,1});
        while(!q.empty())
        {
            auto t=q.front();
            q.pop();
            if(t.first->left!=nullptr)
            {
                q.push({t.first->left,t.second+1});
            }
            if(t.first->right!=nullptr)
            {
                q.push({t.first->right,t.second+1});
            }
            if(t.first->left==nullptr&&t.first->right==nullptr)
            {
                return t.second;
            }
        }
        return -1;
    }  
};

选数(dfs爆搜)

image-1649861869146

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n,k,m,ans;
int a[N];

bool isprime(int x)
{
    for(int i=2;i<=(int )sqrt(x);i++)
    {
        if(x%i==0) return false;
    }
    return true;
} 

void dfs(int num,int sum,int st)
{
    if(num==k)
    {
        if(isprime(sum)) ans++;
        return;
    }

    for(int i=st;i<n;i++)
    {
        dfs(num+1,sum+a[i],i+1);
    }
}

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    dfs(0,0,0);
    cout<<ans<<endl;
}

取数游戏

image-1650026261923

#include<bits/stdc++.h>
using namespace std;
const int N=8;
int n,k,m,ans,sum;
int a[N][N];
int v[N][N];

void dfs(int x,int y)
{   
    if(y>m)
    {

        dfs(x+1,1);
        return;
    }
    if(x>n)
    {
        ans=max(ans,sum);
        return;
    }
    if(v[x][y]==0)
    {
        sum+=a[x][y];
        for(int i=x-1;i<=x+1;i++)
        {
            for(int j=y-1;j<=y+1;j++)
            {
                v[i][j]++;
            }
        }
        dfs(x,y+1);     //当前没访问过,也需要访问下一个
        for(int i=x-1;i<=x+1;i++)
        {
            for(int j=y-1;j<=y+1;j++)
            {
                v[i][j]--;
            }
        }
        sum-=a[x][y];
    }
    dfs(x,y+1);     //当前访问过了,需要访问下一个
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        ans=0;
        memset(a,0,sizeof(a));
        sum=0;
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }
        
        dfs(1,1);
        cout<<ans<<endl;
    }

}

Q.E.D.