迷宫问题
【问题描述】
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式。保证起点上没有障碍。
【输入文件】
第一行N、M和T,N为行,M为列,T为障碍总数。
第二行起点坐标SX,SY,终点坐标FX,FY。
接下来T行,每行为障碍的坐标。
【输出文件】
给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。
【样例输入】
2 2 1
1 1 2 2
1 2
【样例输出】
1
【数据规模】
1<=N,M<=5
【数据分析】
时间与空间复杂度朴素的搜索都可以接受。。
【解题思路】
又是一个标准的搜索,,DFS BFS都能做,,因为是求最短路我比较倾向于BFS,时间会更优。
然后还有一个关键点:起点上没有障碍不代表重点是没有障碍!!其实读入的时候只要障碍的坐标有终点那么直接输出-1就行了。。。如果不这样做的话也未尝不可,中间搜索其实也可以判断好这种情况,,然而我不知道为什么我竟然把判断卡在了外面(⊙o⊙)…,,WA掉真是活该。。。
下面是改过的程序。。。
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sx[4]={1,-1,0,0};
int sy[4]={0,0,1,-1};
int queue[100][4],a[100][100];
int n,m,t,x1,y1,x2,y2,i,x,y,head,tail;
int main()
{
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
scanf("%d%d%d",&n,&m,&t);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for (i=1;i<=t;++i)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
}
head=0;
tail=1;
queue[tail][1]=x1;//queue[i][1]表示横坐标,queue[i][2]表示纵坐标,queue[i][3]表示从起点到达(queue[i][1]
queue[tail][2]=y1;//,queue[i][2])这个点的最少步数
queue[tail][3]=1;//注意根据样例,起点的步数应该是1
while (head<tail)
{
head++;
for (i=0;i<4;++i)//向四个方向走
{
x=queue[head][1]+sx[i];
y=queue[head][2]+sy[i];
if (x>0&&y>0&&x<=n&&y<=m&&a[x][y]==0)
{
tail++;
queue[tail][1]=x;
queue[tail][2]=y;
queue[tail][3]=queue[head][3]+1;
a[x][y]=1;
if (x==x2&&y==y2)//出事的地方!!我竟然把这个if放在了上一个if的外面。。。该打。。
{
printf("%d",queue[tail][3]);
return 0;
}
}
}
}
printf("-1");
return 0;
}
【心得】
调试的时候想想极值和特殊值,,如果想到了就什么事也没有了,,,然后就是以后这种错误不能再犯了啊啊啊( ⊙ o ⊙ )啊!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)