電子老鼠闖迷宮



有一隻電子老鼠被困在如下圖所示的迷宮中。這是一個12*12單元的正方形迷宮，黑色部分表示建築物，白色部分是路。電子老鼠可以在路上向上、下、左、右行走，每一步走一個格子。現給定一個起點S和一個終點T，求出電子老鼠最少要幾步從起點走到終點。

輸入：

本題包含一個測例。在測例的第一行有四個由空格分隔的整數，分别表示起點的坐标S（x.y）和終點的坐标T（x,y）。從第二行開始的12行中，每行有12個字元，描述迷宮的情況，其中'X'表示建築物，'.'表示路.

輸出：

輸出一個整數，即電子老鼠走出迷宮至少需要的步數。

#include<iostream>

#include<queue>

using namespace std;

queue<int> q1;

queue<int> q2;

char map[12][12];//迷宮地圖

int sx,sy,tx,ty;//起點和目标坐标

int dr[4]={0,1,0,-1};//0左1下2右3上

int dc[4]={-1,0,1,0};//0左1下2右3上

int step[12][12];

void readdata();

void init();

int bfs();

int canmoveto(int x,int y,int dire);

int main()

{

 int num;

 readdata();

 init();

 num=bfs();

 cout<<num<<endl;

 return(0);

}

void readdata()

{

 int i,j;

 cin>>sx>>sy>>tx>>ty;

 sx=sx-1;//行

 sy=sy-1;//列

 tx=tx-1;

 ty=ty-1;

 for(i=0;i<12;i++)

 {

  for(j=0;j<12;j++)

  {

   cin>>map[i][j];

  }

 }

}

void init()

{

 q1.push(sx);//行

 q2.push(sy);//列

 step[sx][sy]=0;

}

int bfs()

{

 int ux,uy,vx,vy;

 int i;

 while(!q1.empty()&&!q2.empty())

 {

  ux=q1.front();//行

  uy=q2.front();//列

  q1.pop();

  q2.pop();

  for(i=0;i<4;i++)

  {

   if(canmoveto(ux,uy,i))

   {

    vx=ux+dr[i];

    vy=uy+dc[i];

    if(vy==ty&&vx==tx)

    {

     return(step[ux][uy]+1);

    }

    else

    {

     q1.push(vx);

     q2.push(vy);

     step[vx][vy]=step[ux][uy]+1;

    }

   }

  }

  map[ux][uy]='Q';//标記已走過地方

 }

 return(-1);

}

int canmoveto(int x,int y,int dire)

{

 if(x==0&&dire==3||x==11&&dire==1||y==0&&dire==0||y==11&&dire==2)//判是否越界

 {

  return(0);

 }

 x=x+dr[dire];

 y=y+dc[dire];

 if(map[x][y]=='.')//判是否能走

 {

  return(1);

 }

 else

 {

  return(0);

 }

}