迷宫[洛谷 P1605]
题目
题目背景
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
题目描述
无
输入格式
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出格式
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。
这道题一看就是
灰常简单的搜索
还需要些函数
先撸一下思路
好像没有什么可撸的
直接上代码
函数部分
void dfs(int x,int y)
{
if(x==fx&&y==fy)//判断是否走到终点
{
ans++;//累加
return;
}
else
{
for(int i=0;i<=3;i++)//四种方向
{
int nx=x+dx[i];//x坐标
int ny=y+dy[i];//y坐标
if(tmp[nx][ny]==0&&a[nx][ny]==1)//是否走过 & 是否为陷阱
{
tmp[x][y]=1;
dfs(x+dx[i],y+dy[i]);
tmp[x][y]=0;
}
}
}
}
你可能会问：
if(tmp[nx][ny]==0&&a[nx][ny]==1)//是否走过 & 是否为陷阱
{
tmp[x][y]=1;
dfs(x+dx[i],y+dy[i]);
tmp[x][y]=0;
}
会不会出界
当然是会的
但是你在看if里边
你就会明白
就算出界了
也不会出事
这就是这个代码的
精髓
上代码
#include<iostream>
using namespace std;
int a[10][10];
bool tmp[10][10];
int dx[4]={0,0,1,-1};//x坐标
int dy[4]={-1,1,0,0};//y坐标
int ans,fx,fy,sx,sy,T,n,m,l,r;
void dfs(int x,int y)
{
if(x==fx&&y==fy)//判断是否走到终点
{
ans++;//累加
return;
}
else
{
for(int i=0;i<=3;i++)//四种方向
{
int nx=x+dx[i];//x坐标
int ny=y+dy[i];//y坐标
if(tmp[nx][ny]==0&&a[nx][ny]==1)//是否走过 & 是否为陷阱
{
tmp[x][y]=1;
dfs(x+dx[i],y+dy[i]);
tmp[x][y]=0;
}
}
}
}
int main()
{
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]=1;
for(int u=1;u<=T;u++)
{
cin>>l>>r;
a[l][r]=0;//打个标记
}
dfs(sx,sy);
cout<<ans;
return 0;
}