【算法】深度优先搜索算法DFS

DFS算法

DFS,深度优先搜索,顾名思义,以深度为优先。举一个栗子:

0

1             2

3      4              5

深搜算法的顺序:0-1-3-4-2-5

从0出发,沿着一个分叉点1向下走,然后再沿分叉点3走,再走到3的分叉点4。这时发现4的分叉点1和3都走过了,于是一直回到0,发现0的分叉点2没有走,于是沿着这条分叉一直走到5,遍历完毕。

根据算法原理,程序设计应当具备一个队列数组、标记数组。程序初始化遍历图,生成二维队列数组,从顶点开始检查该点各个方向的点是否可用。只要可用就走,不可用则代表这条路已经到底,反向返回到上一个分叉点。每走一个点标记一个点的坐标为不可用。直到走完最后一个点。

经典DFS迷宫

题目背景

给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

题目描述

输入格式:

第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。

输出格式:

给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。

输入输出样例

输入样例#1

2 2 1
1 1 2 2
1 2

输出样例#1

1

说明

【数据规模】
1≤N,M≤5

AC代码

#include<bits/stdc++.h>
using namespace std;
int q[101][101];
long long sum=0;
int i,j,n,m,t,sx,sy,x,y,ex,ey;
void dfs(int a,int b)
{
    if (a==ex&&b==ey)//如果到了终点 
    {
        sum++;//方案数 + 1 
        return;
    }
    else
    {
        q[a][b]=0;//把当前节点置为已选择 
        if(q[a-1][b]!=0) {dfs(a-1,b);q[a-1][b]=1;}
        if(q[a][b-1]!=0) {dfs(a,b-1);q[a][b-1]=1;}
        if(q[a][b+1]!=0) {dfs(a,b+1);q[a][b+1]=1;}
        if(q[a+1][b]!=0) {dfs(a+1,b);q[a+1][b]=1;}
        //以当前节点为中心向四个方向延伸,直到找不到邻节点或碰到障碍物 
    }
}
int main()
{
    memset(q,0,sizeof(q));//初始化棋盘所有节点为不可用,防止出界
    cin>>n>>m>>t;//n是行 m是列 t是障碍物的个数 
    cin>>sx>>sy>>ex>>ey;// sx sy是起点的坐标 ex ey是终点的坐标 
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            q[i][j]=1;//将迷宫内所有点记为可用
    for(i=1;i<=t;i++)
    {
        cin>>x>>y;
        q[x][y]=0;//把障碍物标为不可用 
    }
    dfs(sx,sy);//把起点作为入参进行DFS 
    cout<<sum<<endl;//方案总数输出
    return 0;
}

题水理不水,这道简单的迷宫题确实对于理解DFS有很大帮助。也是个不错的板子的说~

(题目来自网络)

晓枫

晓枫

苦逼学党,喜欢PHP/Python等开发,V家粉/死宅/杂食动物,工商管理/心理学,欢迎大佬勾搭~⊙ω⊙

留下你的评论

相关推荐

暂无内容!