TIOJ 1392 傳訊兵問題extreme

poao899    296K    2046MS    G++    1.22K     2009-10-12 19:49:34                                           .

唔這題跟1391完全沒關係XD



只是單純的最短路問題XD

我寫spfa速度有變快了好開心XD大概是這題不用建圖吧(咦

不過離開queue忘了處理讓我炸了一次orz


//****************************************************

#include<stdio.h>
#define INF 2147483647
#define qlen 50000
int node[100][100];
int dis[100][100];
int q[qlen][2];
int inq[100][100];
int n,max,front,rear;
int dir[4][2]={{-1,-1},{-1,0},{1,0},{1,1}};
int getint(){
    int g=0;char c=getchar();
    while(c==32||c==10||c==9)c=getchar();
    if(c==EOF)return 0;
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g;
}
main(){
    while(n=getint()){
        max=0;
        front=0;
        rear=1;
        for(int i=0;i<n;i++)
            for(int j=0;j<=i;j++){
                node[i][j]=getint();
                dis[i][j]=INF;
                inq[i][j]=0;
            }
        dis[0][0]=node[0][0];
        q[0][0]=q[0][1]=0;
        inq[0][0]=1;
        while(front!=rear){
            int x=q[front][0],y=q[front][1],nx,ny;
            for(int i=0;i<4;i++){
                nx=x+dir[i][0];
                ny=y+dir[i][1];
                if(ny>nx || nx>=n || nx<0 || ny<0)continue;
                if( ((dis[x][y]>?node[nx][ny])+1) < dis[nx][ny]){
                    dis[nx][ny] = ((dis[x][y]>?node[nx][ny])+1);
                    if(!inq[nx][ny]){
                        q[rear][0]=nx;
                        q[rear][1]=ny;
                        rear=++rear%qlen;
                        inq[nx][ny]=1;
                    }
                }
            }
            inq[x][y]=0;
            front=++front%qlen;
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<=i;j++)
                max>?=dis[i][j];
        printf("%d\n",max);
    }
}