알고리즘 배선 문제

문제 설명: 인쇄 회로 기 판 은 배선 구역 을 n 으로 나 누 었 다.×m 개의 격자 배열, 정확 한 회로 배선 문 제 는 격자 a 에서 격자 b 까지 의 최 단 배선 방안 을 확정 해 야 한다.배선 할 때 회 로 는 직선 이나 직각 (격자) 을 따라 만 배선 할 수 있다.이미 포 선 된 격자 가 잠 겨 있 습 니 다. 즉, 다른 선 로 를 통과 할 수 없습니다.
문제 분석: 시작 위치 a 부터 이 를 첫 번 째 확장 노드 로 하고 이 노드 와 인접 하 며 도착 할 수 있 는 격자 가 실행 가능 한 노드 가 되 어 활성 노드 대기 열 에 가입 하고 이 격자 들 을 1 로 표시 합 니 다. 즉, 시작 격자 a 에서 이 격자 까지 의 거 리 는 1 입 니 다.이 어 활성 점 대기 열 에서 팀 의 첫 번 째 노드 를 꺼 내 다음 확장 점 으로 하고 이때 확장 점 과 인접 하고 표시 되 지 않 은 격자 를 2 로 기록 하고 활성 점 대기 열 에 저장 합 니 다.이 과정 은 알고리즘 이 대상 격자 b 나 활성 점 대기 열 이 비어 있 을 때 까지 계 속 됩 니 다.

#include 
#include 
using namespace std;
#define n 7//    
#define m 7

int a[n][m]={
    0,0,-1,0,0,0,0,
    0,0,-1,-1,0,0,0,
    0,0,0,0,-1,0,0,
    0,0,0,-1,-1,0,0,
    -1,0,0,0,-1,0,0,
    -1,-1,-1,0,0,0,0,
    -1,-1,-1,0,0,0,0
};//            （-1            ）
int s[n][m];//    
int dist = 1;//        

//   （px，py）       ，           
bool AddIntoS(int px,int py,int s[n][m],int a[n][m])
{
    if(px<0||px>n-1||py<0||py>m-1||a[px][py]!=0||s[px][py]==-1)return false;
    a[px][py]=dist;
    s[px][py]=1;
    return true;
}

//            ，  -1        
int FindOfIndexFromS(int s[n][m])
{
    for(int i=0;i0)return i*m+j;
    return -1;
}
//    (sx,sy)，    (ex,ey)
void FindPath(int sx,int sy,int ex,int ey,int s[n][m],int a[n][m])
{
    AddIntoS(sx+1,sy,s,a);
    AddIntoS(sx-1,sy,s,a);
    AddIntoS(sx,sy+1,s,a);
    AddIntoS(sx,sy-1,s,a);//              
    while(true)
    {
        int index=FindOfIndexFromS(s);
        if(index==-1)break;
        int px=index/m,
            py=index%m;
        dist=a[px][py]+1;
        s[px][py]=-1;
        AddIntoS(px+1,py,s,a);
        if(px+1==ex&&py==ey)break;
        AddIntoS(px-1,py,s,a);
        if(px-1==ex&&py==ey)break;
        AddIntoS(px,py+1,s,a);
        if(px==ex&&py+1==ey)break;
        AddIntoS(px,py-1,s,a);
        if(px==ex&&py-1==ey)break;
    }
    int temp=dist-1;
    while(temp>0)//    ，                 1    
    {
        if(a[ex+1][ey]==temp)ex++;
        else if(a[ex-1][ey]==temp)ex--;
        else if(a[ex][ey+1]==temp)ey++;
        else if(a[ex][ey-1]==temp)ey--;
        else {
            cout<