亲宝软件园·资讯

展开

洛谷 p1605 迷宫问题 详解

心不懈 人气:0

 

 题解:dfs搜索

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
using namespace std;
int map[6][6];//地图
bool temp[6][6];//走过的标记
int dx[4]={0,0,1,-1};//打表
int dy[4]={-1,1,0,0};
int sx,sy,fx,fy,total,l,r,n,m;
void walk(int x,int y)//x和y分别表示走到的点
{
    if(x==fx&&y==fy)//如果刚好达到终点,则方案加1
    {
        total++;
        return ;
    }
    else
    {
        for(int i=0;i<=3;i++)//i《=3意思就是四个方向进行遍历
        {
            int a=x+dx[i];//下一个位置
            int b=y+dy[i];
            if(temp[a][b]==0&&map[a][b]==1)//判断没有走过,并且没有障碍
            {
                temp[x][y]=1;//标记
                walk(a,b);//继续搜下一个点
                temp[x][y]=0;//恢复
            }
        }
    }
}
int main ()
{
    int n,m,t;
    cin>>n>>m>>t;
    for(int ix=1;ix<=n;ix++)//把所给的区域变成1
    {
        for(int iy=1;iy<=m;iy++)
        {
            map[ix][iy]=1;
        }

    }
    cin>>sx>>sy>>fx>>fy;
    int l,r;
   for(int u=0;u<t;u++)
   {
       cin>>l>>r;
       map[l][r]=0;//障碍标记成0
   }
   walk(sx,sy);//搜索一般都是起点坐标
   cout<<total;
   return 0;
}

 

加载全部内容

相关教程
猜你喜欢
用户评论