欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【深搜】迷宫

程序员文章站 2022-03-03 11:13:53
...

声明


我的码风可能有点和别人不太一样(其实就是有点奇怪),大家重在意会即可~。
原题传送门

题目


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

输入输出格式

输入格式:

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

输出格式:

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

前言

~~这道题话说是真的水,不过用来练习深搜还是很好的。 ~~这道题十分经典,强烈建议大家自己敲一遍,感受一下这道极其基础的深搜题.

代码详解


为避免繁琐的if语句,先来打个表

const int nextx[4]={0,0,1,-1};
const int nexty[4]={-1,1,0,0};

深搜函数:

void dfs(int x,int y)//深搜 
判断边界:
if(x<1||y<1||x>n||y>m)//如果越界,则返回 
  return;

判断是否到达终点:

if(x==fx&&y==fy)//如果到达终点,则方案数加一 
{
    ans++;
    return;
}

搜索与回溯(重点):

b[x][y]=true;//将当前点标记为已访问 
for(int i=0;i<=3;i++)        
    if(b[x+nextx[i]][y+nexty[i]]==false&&a[x+nextx[i]][y+nexty[i]]==true)//如果未访问且不是障碍物    
        dfs(x+nextx[i],y+nexty[i]);    //则继续深搜 
b[x][y]=false;//回溯 

深搜的完整函数:

void dfs(int x,int y)//深搜 
{
    if(x<1||y<1||x>n||y>m)//如果越界,则返回 
        return;
    if(x==fx&&y==fy)//如果到达终点,则方案数加一 
    {
        ans++;
        return;
    }
    b[x][y]=true;//将当前点标记为已访问 
    for(int i=0;i<=3;i++)        
        if(b[x+nextx[i]][y+nexty[i]]==false&&a[x+nextx[i]][y+nexty[i]]==true)//如果未访问且不是障碍物    
            dfs(x+nextx[i],y+nexty[i]);    //则继续深搜 
    b[x][y]=false;//回溯 
}

完整AC代码


你们最爱的AC代码~~~

#include <iostream>
using namespace std;
bool a[10][10];
bool b[10][10]={0};
int n,m,t,sx,sy,fx,fy,ans=0;
const int nextx[4]={0,0,1,-1};
const int nexty[4]={-1,1,0,0};
  
void dfs(int x,int y)//深搜 
{
     if(x<1||y<1||x>n||y>m)//如果越界,则返回 
         return;
     if(x==fx&&y==fy)//如果到达终点,则方案数加一 
     {
         ans++;
         return;
     }
     b[x][y]=true;//将当前点标记为已访问 
     for(int i=0;i<=3;i++)        
         if(b[x+nextx[i]][y+nexty[i]]==false&&a[x+nextx[i]][y+nexty[i]]==true)//如果未访问且不是障碍物    
             dfs(x+nextx[i],y+nexty[i]);    //则继续深搜 
     b[x][y]=false;//回溯 
}
int main()
{
     int tx,ty;
     cin>>n>>m>>t>>sx>>sy>>fx>>fy;
     for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
             a[i][j]=true;
     for(int i=1;i<=t;i++)
     {
         cin>>tx>>ty;
         a[tx][ty]=false;
     }
     b[sx][sy]=true;
     dfs(sx,sy);
     cout<<ans;//输出结果 
     return 0;
}

后记


这道题由于我手残,敲完代码时不小心关了...关了...于是重打一了遍,浪费了不少时间,不过这些都不重要~ ~ ~各位大佬们看到这里,能否给个赞呢?~>_< ~