最短経路の回路配線を解く

aとbの間の最短経路は、2つのプロセスで決定する必要がある.1つは距離タグプロセスであり、もう1つは経路タグプロセスである.距離マーキングの過程では、まず位置aから、aから到達可能な隣接格子を1(aから距離が1であることを示す)とマーキングし、次に、1である格子から到達可能な隣接格子を2(aが2であることを示す)とマーキングする.このマーキングプロセスは、bに到達するか、隣接する格子に到達できないまで継続する.タグ処理が終了すると、パスタグ処理が開始します.四角い格子bからまず、bの番号より1小さい隣の位置に移動する.この過程をaに達するまで繰り返す.距離タグプロセスを実現するために,別の配列を用いて距離を格納したり,配列gridを再利用したりすることができる.メモリを節約するために配列再利用を一般的に使用しますが、障害物は距離1の四角形と混合されるので、すべての距離フラグに2を追加することを選択します.

bool findpath()
{
    if((start.row==finish.row)&&(start.col==finish.col))
    {
        pathLength=0;
        return true;
    }
    position offset[4];
    offset[0].row=0;offset[0].col=1;// 
    offset[1].row=1;offset[1].col=0;// 
    offset[2].row=0;offset[2].col=-1;// 
    offset[3].row=-1;offset[3].col=0;// 

    //        weiqiang
    for(int i=0;i<=size+1;i++)
    {
        grid[0][i]=grid[size+1][i]=1;//     
        grid[i][0]=grid[i][size+1]=1;//     
    }
    position here=start;
    grid[start.row][start.col]=2;
    int numOfNbrs=4;
    //         
    arrayQueueq;
    position nbr;
    do{
        //        
        for(int i=0;i//      
            nbr.row=here.row+offset[i].row;
            nbr.col=here.col+offset[i].col;
            if(grid[nbr.row][nbr.col]==0)
            {
                grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
                if((nbr.col==finish.row)&&(nbr.col==finish.col))
                    break;
                q.push(nbr);
            }

        }
        if((nbr.row==finish.row)&&(nbr.col==finish.col))break;
        if(q.empty())
            return false;
        here=q.front();
        q.pop();        
    }while(true);

    //    
    pathLength=grid[finish.row][finish.col]-2;
    path=new position[pathLength];

    //     
    here=finish;
    for(int j=pathLength-1;j>=0;j--)
    {
        path[j]=here;
        for(int i=0;iif(grid[nbr.row][nbr.col]==j+2)break;
        }
        here=nbr;
    }
    return true;
}

コード解析:まず、開始点の周囲の0点(マークできる点)を1つ追加し、周囲のマークされた点をキューに挿入し、キューヘッダから1つの点を抽出して削除し、その周囲のマーク可能な点を1つ追加します.キューが空か、終了点に到達していることがわかります.その後、終了点から遡及が開始され、前の位置より1つ少ないノードが検索されるたびにタグが検索されます.開始点まで.