[题解+总结]20150816.

1、前言

同样是搜索题，感觉今天的鬼畜多了，还出现了一道标程都莫名其妙的题目。。。

2、Maze 迷宫

大概题意：在一个0-1矩阵中给出起始点和终点，求最短路径。（0为可走，1为不可走）

总结：边界条件出了问题导致WA+RE了20分。我们可以把外围所有点设置为1（不可走），也可以在搜索时添加判断。还有一个很重要的问题，2000*2000的数据在读入时极有可能会超时，建议用读入优化。

题解：最短路径推荐直接BFS。

代码：

-------------------------------------------------------------------------------------

#include<cstdio>
#include<cstdlib>
#define MAXN 2005
#define INF 1<<30

int max(int a,int b) { return (a>b)?a:b; }

struct Queue
{
　　int x,y;
};
Queue q[MAXN*MAXN];

const int vx[5]={0,-1,1,0,0};
const int vy[5]={0,0,0,-1,1};

int map[MAXN][MAXN],n,m,sx,sy,tx,ty;

int check(int now)
{
　　if (q[now].x==tx && q[now].y==ty) printf("%d",map[q[now].x][q[now].y]-1),exit(0);
}

void BFS()
{
　　int head=1,tail=2; q[head].x=sx,q[head].y=sy,map[sx][sy]=1;
　　while (head!=tail)
　　{
　　　　int nx=q[head].x,ny=q[head].y;
　　　　for (int i=1;i<=4;i++)
　　　　　　if (map[nx+vx[i]][ny+vy[i]]==0)
　　　　　　{
　　　　　　　　map[nx+vx[i]][ny+vy[i]]=map[nx][ny]+1;
　　　　　　　　q[tail].x=nx+vx[i],q[tail].y=ny+vy[i];
　　　　　　　　check(tail),tail++;
　　　　　　}
　　　　head++;
　　}
}

int main()
{
　　freopen("maze.in","r",stdin);
　　freopen("maze.out","w",stdout);
　　scanf("%d %d",&n,&m);
　　for (int i=1;i<=n;i++)
　　　　for (int j=1;j<=m;j++)
　　　　{
　　　　　　scanf("%d",&map[i][j]);
　　　　　　map[i][j]=(!map[i][j])?0:-1;
　　　　}　　
　　for (int i=1;i<=max(n,m);i++) map[0][i]=map[i][0]=map[n+1][i]=map[i][m+1]=-1;
　　scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
　　BFS();
　　printf("No Answer!");
　　return 0;
}

-------------------------------------------------------------------------------------

[题解+总结]20150816.

原文：http://www.cnblogs.com/jinkun113/p/4738012.html