洛谷 P1605 迷宫
题目链接
https://www.luogu.org/problemnew/show/P1605
题目背景
迷宫
题目描述
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和
终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫
中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
输入输出格式
输入格式：
【输入】
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点
坐标FX,FY。接下来T行，每行为障碍点的坐标。
输出格式：
【输出】
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方
案总数。
【数据规模】
1≤N,M≤5
思路
一道连小小小小（此处省略999999个小）蒟蒻都会的搜索水题，却卡了我大半个小时......
原因就是边界条件忘记判断了......（不对，还RE了几次）
建立二维BOOL数组a和vis，a数组表示大地图（赋初值后不再改变），而vis数组则是每次搜索时进行标记和回溯的数组
按要求输入，并将障碍点全部标记为true,不要忘记把起始点也标记为true，然后进行搜索，判断即可
如果搜到了（fx,fy）这个点，就让tot++，最后输出即可
代码
#include<bits/stdc++.h>//还是懒人头文件
using namespace std; int n,m,t;
bool a[][],vis[][];
int x,y;
int sx,sy,fx,fy;//题目要求输入的对象
int f[][]= {{,,},{,,},{,,-},{,,},{,-,}};
int tot=;//答案 /*
inline int read() {
char ch=getchar();
int x=0,f=1;
while(ch<'0'||ch>'9') {
if(ch=='-');
f=-1,ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-48,ch=getchar();
}
return x*f;
}
*/ void dfs(int x,int y) {
if(x==fx&&y==fy) {//找到了就加一再回溯
tot++;
return;
}
for(int i=; i<=; i++) {
int nx=x+f[i][];
int ny=y+f[i][];
if(nx>&&ny>&&nx<=n&&ny<=m&&!a[nx][ny]&&!vis[nx][ny]) {
vis[nx][ny]=true;
dfs(nx,ny);
vis[nx][ny]=false;
}
}
} int main() {
memset(a,false,sizeof(a));
scanf("%d%d%d",&n,&m,&t);
scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
a[sx][sy]=true;//出发点为true
while(t--) {
scanf("%d%d",&x,&y);
a[x][y]=true;
}
dfs(sx,sy);//搜索
cout<<tot<<endl;
return ;
}