uva 929 Number Maze

把這張格子的圖想成是一張無向圖，連結的部分只有四個方向的小格子。

只要做 dijkstra 算出左上角到右下角的最短距離即為解。

judge 時，發現到：

counter 存筆數，while(counter--)在 uva 上跑的時候，不會終止。要改成其它方式跳出。


#include <stdio.h>
#include <stdlib.h>

struct node{
    int x;
    int y;
    int distance;
};


int maze[1000][1000]={0};
int row,column,amount;
int ans;
struct node * minHeap;
int *table;

void adjust(int index){
    struct node tmp;

    int parent,child;

    child=index;
    parent=index/2;

    tmp=minHeap[index];
    while(parent>=1){
        if(minHeap[parent].distance > tmp.distance){
            minHeap[child]=minHeap[parent];
            table[minHeap[child].x*1000 + minHeap[child].y]=child;
        }else
            break;

        child=parent;
        parent=child/2;
    }
    minHeap[child]=tmp;
    table[minHeap[child].x*1000+minHeap[child].y]=child;

    return;
}

struct node extract(){
    struct node tmp,change;
    int index,parent,child;

    tmp.distance=-1;

    if(amount==0) return tmp;

    tmp=minHeap[1];
    maze[tmp.x][tmp.y]=-1;

    change=minHeap[amount];
    --amount;

    parent=1;
    child = parent*2;
    while(child<=amount){
        if(child < amount){
            if(minHeap[child].distance > minHeap[child+1].distance)
                ++child;
        }

        if(change.distance > minHeap[child].distance){
            minHeap[parent]=minHeap[child];
            table[minHeap[parent].x*1000+minHeap[parent].y]=parent;
        }else
            break;

        parent=child;
        child=parent*2;
    }
    minHeap[parent]=change;
    table[minHeap[parent].x*1000+minHeap[parent].y]=parent;

    return tmp;
}

void dijkstra(){
    struct node tmp;

    minHeap[1].distance=maze[1][1];
    while(1){
        tmp=extract();
        if(tmp.x==row&&tmp.y==column){ ans=tmp.distance; return; }


        if( (tmp.x-1)>=1 && (tmp.y)>=1 && maze[tmp.x-1][tmp.y]!=-1)
            if(tmp.distance + maze[tmp.x-1][tmp.y] < minHeap[table[(tmp.x-1)*1000+tmp.y]].distance){
                minHeap[table[(tmp.x-1)*1000+tmp.y]].distance=tmp.distance + maze[tmp.x-1][tmp.y];
                adjust(table[(tmp.x-1)*1000+tmp.y]);
            }
        if( (tmp.x)>=1 && (tmp.y+1)<=column && maze[tmp.x][tmp.y+1]!=-1)
            if(tmp.distance + maze[tmp.x][tmp.y+1] < minHeap[table[tmp.x*1000+tmp.y+1]].distance){
                minHeap[table[tmp.x*1000+tmp.y+1]].distance=tmp.distance + maze[tmp.x][tmp.y+1];
                adjust(table[tmp.x*1000+tmp.y+1]);
            }
        if( (tmp.x+1)<=row && (tmp.y)>=1 && maze[tmp.x+1][tmp.y]!=-1)
            if(tmp.distance + maze[tmp.x+1][tmp.y] < minHeap[table[(tmp.x+1)*1000+tmp.y]].distance){
                minHeap[table[(tmp.x+1)*1000+tmp.y]].distance=tmp.distance + maze[tmp.x+1][tmp.y];
                adjust(table[(tmp.x+1)*1000+tmp.y]);
            }
        if( (tmp.x)>=1 && (tmp.y-1)>=1 && maze[tmp.x][tmp.y-1]!=-1)
            if(tmp.distance + maze[tmp.x][tmp.y-1] < minHeap[table[tmp.x*1000+tmp.y-1]].distance){
                minHeap[table[tmp.x*1000+tmp.y-1]].distance=tmp.distance + maze[tmp.x][tmp.y-1];
                adjust(table[tmp.x*1000+tmp.y-1]);
            }
    }


    return;
}

int main(void){
    int i,j,index,counter;

    minHeap = (struct node *)malloc( sizeof(struct node) * 1000 * 1000 );
    table = (int *)malloc( sizeof(int) * 1000 * 1000 );

    scanf("%d",&counter);
    while(counter--){
        scanf("%d",&row);
        scanf("%d",&column);

        amount=row*column;

        for(i=1,index=0;i<=row;i++){
            for(j=1;j<=column;j++){
                scanf("%d",&maze[i][j]);
                minHeap[++index].distance=100000;
                minHeap[index].x=i;
                minHeap[index].y=j;

                table[i*1000+j]=index;
            }
        }

        ans=0;
        dijkstra();

        printf("%d\n",ans);

        if(counter<= 0)break;
    }

    return 0;
}