1042.电子老鼠闯迷宫

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点S和一个终点T，求出电子老鼠最少要几步从起点走到终点。

输入

本题包含一个测例。在测例的第一行有四个由空格分隔的整数，分别表示起点的坐标S（x.y）和终点的坐标T（x,y）。从第二行开始的12行中，每行有12个字符，描述迷宫的情况，其中'X'表示建筑物，'.'表示路.

输出

输出一个整数，即电子老鼠走出迷宫至少需要的步数。

输入样例

2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX

输出样例

28

#include <stdio.h>
#include <string.h>

struct note
{
    int x;//横坐标
    int y;//纵坐标
    int s;//步数
};


int main()
{

   struct note que[145];

   int book[13][13] = {0};
   char a[13][13];

   int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

   int head,tail;
   int i,k,n=12,m=12,startx,starty,p,q,tx,ty,flag;

   scanf("%d %d %d %d",&startx,&starty,&p,&q);
   getchar();
    for(i=1;i<=n;i++)
     gets(a[i]);
   //队列初始化
   head = 1;
   tail = 1;

   //往队列插入迷宫入口坐标
   que[tail].x = startx;
   que[tail].y = starty;
   que[tail].s = 0;
   tail++;
   book[startx][starty] = 1;

   flag = 0;//用来标记是否到达目标点，0表示暂未，1表示到达

   //当队列不为空时循环
   while(head<tail)
   {
          //枚举四个方向
       for (k=0;k<=3;k++)
       {
           //计算下一个点的坐标
           tx = que[head].x+next[k][0];
           ty = que[head].y+next[k][1];
           //判断是否越界
           if (tx<1||tx>n||ty<1||ty>m)
           {
               continue;
           }
           if(a[tx][ty]=='.'&&book[tx][ty]==0)
           {
               book[tx][ty] = 1;
               que[tail].x = tx;
               que[tail].y = ty;
               que[tail].s = que[head].s+1;
               tail++;
           }
           if (tx==p&&ty==q)
           {
               flag = 1;
               break;
           }
       }
       if (flag == 1)
   {
       break;
   }
   head++;
   }

   printf("%d\n",que[tail-1].s);

   return 0;
}
/*
6 6 11 11
XXXXXXXXXXXX
X..........X
X.XXXXXXXX.X
X.X......X.X
X.X.XXXX.X.X
X.X.X..X.X.X
X.X.XX.X.X.X
X.X.XX.X.X.X
X.X....X.X.X
X.XXXXXX.X.X
X........X.X
XXXXXXXXXXXX
58
*/
/*
11 11 4 4
XXXXXXXXXXXX
X........XXX
X.XXXXXX...X
X...XX.XXX.X
X.XXXX.....X
X.X..X..X.XX
X.X....XX.XX
X...XX..X.XX
X..XXXX.X.XX
X.XXXX.....X
X..X...XXX.X
XXXXXXXXXXXX
20
*/[code]

[/code]
最后两个测例，WA！！！

#include<iostream>
#include<queue>
using namespace std;

void bfs();

int x1,y1,x2,y2;
int used[50][50]={0} ;
int s[20][20]={0};
char route[20][20]={0};

queue <int> x;
queue <int> y;                    //在这里需要考虑一个二维的情况，故需要给x，y各一个队列

int main()
{
    int i,j;
     cin>>x1>>y1>>x2>>y2;
    x.push(x1);
    y.push(y1);                    //相当于识别起始位置

    for(i=1;i<=12 ;i++)
    {
        for(j=1;j<=12;j++)
        {
            cin>>route[i][j];
        }
    }

    bfs();
     return 0;
}

void bfs()
{
    int i,j,flag=1;
    while(flag == 1)
    {
        if(s[x2][y2] != 0)                //在没走到终点之前，终点位置的数值始终为0
        //一旦发现不是0了，说明计数已经“计到了”这个位置。当前数值也就代表了步数
        //因为采取了广搜，所以不必担心，首先到达终点的情况肯定是“最小步数”的情况

        {
            cout<<s[x2][y2]<<endl;
            break;
        }

        x1=x.front();
        y1=y.front();        //(x1,y1)始终为当前所在的位置
        x.pop();
        y.pop();
        used[x1][y1]=1;        //走过的不能重复走了！！！！！ 之前忘了这个，结果走了很多重复的路！！！！！！！！！！！
        if(route[x1-1][y1] == '.'&&used[x1-1][y1]==0)        //向上走得通
        {
            x.push(x1-1);
            y.push(y1);
            s[x1-1][y1]=s[x1][y1]+1;
        }

        if(route[x1+1][y1] == '.'&&used[x1+1][y1]==0)        //向下走得通
        {
            x.push(x1+1);
            y.push(y1);
            s[x1+1][y1]=s[x1][y1]+1;
        }

        if(route[x1][y1-1] == '.'&&used[x1][y1-1]==0)        //向左走得通
        {
            x.push(x1);
            y.push(y1-1);
            s[x1][y1-1]=s[x1][y1]+1;
        }

        if(route[x1][y1+1] == '.'&&used[x1][y1+1]==0)        //向右走得通
        {
            x.push(x1);
            y.push(y1+1);
            s[x1][y1+1]=s[x1][y1]+1;
        }

    }
}