Morris' Blog

2011-04-07 13:39:54Morris

d747. 迷宮路徑

留言 0 收藏 0 推薦 0

內容：

在 N*N 的地圖中

求出座標 ( A , B ) → ( X , Y ) 的最短路徑 (只能上下左右走)

地圖中，以 " X " 代表牆壁，測資中四周都有牆壁

輸入說明：

輸入只有一組測資
第一行有兩個數字N M( 1 ≦ N ≦ 1000 ， 1 ≦ M ≦ 500 )
N 代表 N*N 的地圖

M 代表接下來詢問求出座標 ( A , B )→ ( X , Y ) 的最短路徑的次數

接下來會有 M 行，每行上會有 4 個數字 A , B , X , Y (1≦ A,B,X,Y ≦N)

輸出說明：

請求出座標 ( A , B ) → ( X , Y )的最短路徑
如果本來就是牆壁的話，請輸出 "ERROR"(不包含"")
如果沒辦法到達的話，請輸出 "-1"(不包含"")

012345678
0XXXXXXXX
1X............
2XC...........
3X.............

C的位置代表 ( 2 , 1 )

範例輸入：

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

12 2
XXXXXXXXXXXX
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
X..........X
XXXXXXXXXXXX
6 6 3 3
2 1 10 10

範例輸出：

6
17
/**********************************************************************************/
/*  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;
}