TIOJ 1133 Dark Teleport Field [Brute Force]

    poao899    108K    15MS    G++     2.44K     2010-03-28 14:23:25                             .


Debug超超超久orz


原來是兩個矩形的距離算錯

這題只是很暴力不難才對啊orzzzzzzzzzzzzzz








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

#include<stdio.h>
#define QLEN 2000
#define MAXV 160
#define MAXK 10
int d[MAXV][MAXV],dist[MAXV][MAXK];
struct rec{
    int x1,y1,x2,y2;
    void get(){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    }
    int dist(int x,int y){
        int d=0;
        if(x<x1||x>x2)x<x1? d+=x1-x: d+=x-x2;
        if(y<y1||y>y2)y<y1? d+=y1-y: d+=y-y2;
        return d;
    }
}r[200];
//0 st  1~m rec  m+1 ed
int q[QLEN][2],front,rear,n,m,t,k,sx,sy,ex,ey;
bool inq[MAXV][MAXK];
int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=1; i<=m; i++)
            r[i].get();
        for(int i=1; i<=m; i++)
            for(int j=1; j<=m; j++){
                d[i][j]= 2147483647;
                if(d[i][j]> r[i].dist(r[j].x1, r[j].y1))
                    d[i][j]= r[i].dist(r[j].x1, r[j].y1);
                if(d[i][j]> r[i].dist(r[j].x2, r[j].y1))
                    d[i][j]= r[i].dist(r[j].x2, r[j].y1);
                if(d[i][j]> r[i].dist(r[j].x2, r[j].y2))
                    d[i][j]= r[i].dist(r[j].x2, r[j].y2);
                if(d[i][j]> r[i].dist(r[j].x1, r[j].y2))
                    d[i][j]= r[i].dist(r[j].x1, r[j].y2);
                   
                if(d[i][j]> r[j].dist(r[i].x1, r[i].y1))
                    d[i][j]= r[j].dist(r[i].x1, r[i].y1);
                if(d[i][j]> r[j].dist(r[i].x2, r[i].y1))
                    d[i][j]= r[j].dist(r[i].x2, r[i].y1);
                if(d[i][j]> r[j].dist(r[i].x2, r[i].y2))
                    d[i][j]= r[j].dist(r[i].x2, r[i].y2);
                if(d[i][j]> r[j].dist(r[i].x1, r[i].y2))
                    d[i][j]= r[j].dist(r[i].x1, r[i].y2);
            }
        scanf("%d",&t);
        while(t-->0){
            scanf("%d%d%d%d%d",&k,&sx,&sy,&ex,&ey);
            //init
            front=0; rear=1;
            for(int i=0;i<MAXV;i++){
                for(int j=0;j<MAXK;j++){
                    inq[i][j]=0;
                    dist[i][j]=1000000000;
                }
            }
            for(int i=1;i<=m;i++){
                d[i][0]=d[0][i]=r[i].dist(sx,sy);
                d[i][m+1]=d[m+1][i]=r[i].dist(ex,ey);
            }
            d[0][m+1]= d[m+1][0]= (sx>ex? sx-ex: ex-sx)+ (sy>ey? sy-ey: ey-sy);
            q[front][0]= q[front][1]= dist[0][0]= 0; inq[0][0]= 1;
            while(front!=rear){
                int now=q[front][0], dep=q[front][1];
                if(dep<=k){
                    for(int i=1; i<=m; i++){
                        if(dist[i][dep+1]> dist[now][dep]+d[now][i]){
                            dist[i][dep+1]= dist[now][dep]+d[now][i];
                            if(!inq[i][dep+1]){
                                q[rear][0]=i;
                                q[rear][1]=dep+1;
                                inq[i][dep+1]=1;
                                rear=++rear%QLEN;
                            }
                        }
                    }
                    if(dist[m+1][dep]> dist[now][dep]+d[now][m+1])
                        dist[m+1][dep]= dist[now][dep]+d[now][m+1];
                    inq[now][dep]=0;
                }
                front=++front%QLEN;
            }
            int min=2147483647;
            for(int i=0;i<=k;i++)
                if(min> dist[m+1][i])
                    min= dist[m+1][i];
            printf("%d\n",min);
        }
    }
}