洛谷 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[50][50],vis[50][50]; int x,y; int sx,sy,fx,fy;//题目要求输入的对象 int f[5][3]= {{0,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}}; int tot=0;//答案 /* 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=1; i<=4; i++) { int nx=x+f[i][1]; int ny=y+f[i][2]; if(nx>0&&ny>0&&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 0; }
投递旷视等公司10个岗位 >