p3669.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
const int MAXN=302;
const int MAXM=50010;
const int move[4][2]={-1,0,1,0,0,-1,0,1};
struct Arr{
    int x,y,t;
} a[MAXM];
bool sur[MAXN][MAXN],can[MAXN][MAXN];
int q[MAXN*MAXN][3];
int n,i,j,f,c,x,y;
int main(){
    bool ok(int,int,bool[][MAXN]);
    bool cmp(Arr,Arr);
    memset(sur,true,sizeof(sur));
    memset(can,true,sizeof(can));
    ifstream fin("meteor.in");
    fin>>n;
    for(i=0;i<n;i++){
        fin>>a[i].x>>a[i].y>>a[i].t;
        sur[a[i].x][a[i].y]=false;
        for(j=0;j<4;j++)
            if(ok(a[i].x+move[j][0],a[i].y+move[j][1],sur)) sur[a[i].x+move[j][0]][a[i].y+move[j][1]]=false;
    }    
    sort(a,a+n,cmp);
    f=0; c=0; i=0; q[f][0]=0; q[f][1]=0; q[f][2]=0; can[0][0]=false;
    while(f<=c){
        while(i<=n && a[i].t==q[f][2]+1){
            x=a[i].x; y=a[i].y;
            can[x][y]=false;
            for(j=0;j<4;j++)
                if(ok(x+move[j][0],y+move[j][1],can)) can[x+move[j][0]][y+move[j][1]]=false;
            ++i;
        }
        x=q[f][0]; y=q[f][1];
        for(j=0;j<4;j++)
            if(ok(x+move[j][0],y+move[j][1],can)){
                ++c;
                q[c][0]=x+move[j][0];
                q[c][1]=y+move[j][1];    
                q[c][2]=q[f][2]+1;
                can[q[c][0]][q[c][1]]=false;
                if(sur[q[c][0]][q[c][1]]){ cout<<q[c][2]<<endl; system("pause");return 0; }
            }
        ++f;
    }
    cout<<-1<<endl;
    return 0;
}            
bool ok(int x,int y,bool arr[][MAXN]){
    return(x>=0 && x<=MAXN-1 && y>=0 && y<=MAXN-1 && arr[x][y]);
}
bool cmp(Arr i,Arr j){
    return i.t<j.t;
}