题目链接：

解题报告：

网格中的BFS，最主要的是边界问题。

1、这里在左右，上下两个方向上，分别判断墙，和门，细节是，向上有t个墙，for(int j=0;j<t;j++) ya[x][y+1+j]=WALL;   ymax=max(y+t+1,ymax);xmax=max(x+1,xmax);

2、这里采用的是逆向BFS，从dis[1][1]出发，输出dis[tx][ty];

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define MAXV 210#define INF 1<<29#define min(a,b) (a>b?b:a)#define max(a,b) (a>b?a:b)#define EMPTY 0#define DOOR 1#define WALL INFint xa[MAXV][MAXV];     ///在x方向上添上墙int ya[MAXV][MAXV];     ///在y方向上添上墙int dis[MAXV][MAXV];    ///目标答案，dis[i][j]先初始化为无穷，然后置dis[1][1]为0，                        ///根据x,y方向上的是否有墙，自增，没有墙置+0，有门+1，dis[tx][ty]也就是答案int dt[4][2]= {
    {-1,0},{
    1,0},{
    0,-1},{
    0,1}};      ///四个方向分别是向上，向下，向左，向右int xmax,ymax;          ///x,y方向上的边界///判断是否在图表中bool pd(int x,int y){    if(x>0 && x<=xmax && y<=ymax && y>0) return 1;    return 0;}int getvalue(int x,int y,int i){    if(i==0) return ya[x-1][y];    if(i==1) return ya[x][y];    if(i==2) return xa[x][y-1];    return xa[x][y];}///逆向广搜int bfs(int tx,int ty){    int i,j,vx,vy,dx,dy,tmp;    queue 
          
           q;    ///初始化    for(i=1; i<=ymax; i++)    {        for(j=1; j<=xmax; j++)            dis[i][j]=INF;    }    dis[1][1]=0;    q.push(1);    q.push(1);    while(!q.empty())    {        vx=q.front();        q.pop();        vy=q.front();        q.pop();        for(i=0; i<4; i++)        {            dx=vx+dt[i][0];            dy=vy+dt[i][1];            tmp=getvalue(vx,vy,i);      ///tmp为这个格子是否为墙，门，什么都没有，分别对应inf,1,0            if(pd(dx,dy) && dis[dx][dy]>dis[vx][vy]+tmp)            {                dis[dx][dy]=dis[vx][vy]+tmp;                q.push(dx);                q.push(dy);            }        }    }    return (dis[tx][ty]==INF?-1:dis[tx][ty]);}int main(){    int n,m,i,j;    int x,y,d,t;    double sx,sy;    while(scanf("%d%d",&m,&n))    {        ///m个墙，n个门        if(m==-1 && n==-1) break;        ymax=xmax=-1;        memset(xa,EMPTY,sizeof(xa));        memset(ya,EMPTY,sizeof(ya));        for(i=0; i
           
            =1 && sx<=199 && sy>=1 && sy<=199)) printf("0\n"); else printf("%d\n",bfs((int)sx+1,(int)sy+1)); } return 0;}
           
          
         
        
       
      

参考：