Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

/**********************************************************************************/
/*  Problem: d747 "迷宮路徑" from A* (A-star)                                 */
/*  Language: C                                                                   */
/*  Result: AC (476ms, 4837KB) on ZeroJudge                                       */
/*  Author: morris1028 at 2011-04-07 13:37:12                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
struct  Heap {
    short x, y;
    int F;
}Heap[1000000], T;
struct  Mark {
    short x, y;
}Mark[1000000];
int CntStep[1000][1000]={0};
int Sx, Sy, Gx, Gy, dx1, dy1, dx2, dy2, L;
char Map[1000][1001];
/*Heap以下*/
void Swap(int P, int S) {
    T=Heap[P], Heap[P]=Heap[S], Heap[S]=T;
}
void Insert () {
    int S=L, P=L/2;
    while(S >= 2 && Heap[P].F > Heap[S].F)
        Swap(P,S), S=P, P=S/2;
}

void Delete () {
    int P=1, S=2*P;
    Swap(1, L), L--;
    while(S <= L) {
        if(S < L && Heap[S+1].F < Heap[S].F)  S++;
        if(Heap[P].F <= Heap[S].F)  break;
        Swap(P, S), P=S, S=2*P;
    }
}
/*Heap以上*/
/*A-Star以下*/
int H(int Cx, int Cy) {
    dx1=Cx-Gx, dy1=Cy-Gy;
    return abs(dx1*dy2-dx2*dy1)+(abs(Cx-Gx)+abs(Cy-Gy))*1000000;
}
void Judge(int Nx, int Ny, int Cx, int Cy) {
    if(Map[Nx][Ny]!='X' && (CntStep[Nx][Ny]>CntStep[Cx][Cy]+1 || CntStep[Nx][Ny]==0))
        CntStep[Nx][Ny]=CntStep[Cx][Cy]+1,
        Heap[++L].F=CntStep[Nx][Ny]*1000000+H(Nx,Ny), Heap[L].x=Nx, Heap[L].y=Ny,
        Insert();
}
void A_Star (int Sx, int Sy, int Gx, int Gy) {
    
    if(Map[Sx][Sy]=='X' || Map[Gx][Gy]=='X') {
        puts("ERROR");
        return;
    }
    int a, Cx, Cy, Mt=0;
    L=1, dx2=Sx-Gx, dy2=Sy-Gy, Heap[1].x=Sx, Heap[1].y=Sy;
    while(L > 0) {
        Cx=Heap[1].x, Cy=Heap[1].y;
        Mark[Mt].x=Cx, Mark[Mt++].y=Cy;
        if(Cx == Gx && Cy == Gy) break;
        Delete();   
        Judge (Cx+1, Cy, Cx, Cy);
        Judge (Cx-1, Cy, Cx, Cy);
        Judge (Cx, Cy+1, Cx, Cy);
        Judge (Cx, Cy-1, Cx, Cy);
    }
    printf("%d\n", CntStep[Gx][Gy]-(!CntStep[Gx][Gy]));
    /*clear record*/
    for(a = 0; a < Mt; a++)   CntStep[Mark[a].x][Mark[a].y]=0;
    for(a = 1; a <= L; a++)   CntStep[Heap[a].x][Heap[a].y]=0;
}
/*A-Star以上*/
main() {
    int N, M, a;
    scanf("%d %d",&N, &M); {
        getchar();
        for(a = 0; a < N; a++)  gets(Map[a]);
        for(a = 0;  a< M; a++)
            scanf("%d %d %d %d",&Sx,&Sy,&Gx,&Gy), A_Star(Sx,Sy,Gx,Gy);
    }
    return 0;
}