26-伪代码详解

6.4.4　伪代码详解

（1）根据算法设计中的数据结构，首先定义一个结构体Position

typedef struct
{
     int x;
     int y;
} Position;//位置

（2）再定义一个方向数组

Position DIR[4],here,next;// 定义方向数组DIR[4]，当前格here,下一格next;
DIR[0].x=0;
DIR[0].y=1;
DIR[1].x=1;
DIR[1].y=0;
DIR[2].x=0;
DIR[2].y=-1;
DIR[3].x=-1;
DIR[3].y=0;

（3）按4个方向进行搜索

for(;;)
     {
          for(int i=0; i<4; i++)//四个方向的前进,右下左上
          {
               next.x=here.x+DIR[i].x;
               next.y=here.y+DIR[i].y;
               if(grid[next.x][next.y]==-1)//尚未布线
               {
                    grid[next.x][next.y]=grid[here.x][here.y]+1;
                    Q.push(next);
               }
               if((next.x==e.x)&&(next.y==e.y))break;//找到目标
          }
          if((next.x==e.x)&&(next.y==e.y))break;//找到目标
          if(Q.empty()) return false;
          else
          {
               here=Q.front();
               Q.pop();
          }
     }

（4）逆向找回最短布线方案

PathLen=grid[e.x][e.y];//逆向找回最短布线方案
     path=new Position[PathLen];
     here=e;
     for(int j=PathLen-1; j>=0; j--)
     {
          path[j]=here;
          for(int i=0; i<4; i++)//沿四个方向寻找,右下左上
          {
               next.x=here.x+DIR[i].x;
               next.y=here.y+DIR[i].y;
               if(grid[next.x][next.y]==j)break;//找到相同数字
          }
          here=next;
     }