Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一次 AC 奉献代码#include <iostream> #include <queue> using namespace std; #define MAX(a,b) (a>b ? a:b) const int INF=100000000; const int MAX_SIZE=256; struct State { int x,y; int c; bool operator < (const State &a) const { return a.c<c; } }; priority_queue<State> qu; int vE[MAX_SIZE][MAX_SIZE]; int hE[MAX_SIZE][MAX_SIZE]; int dist[MAX_SIZE][MAX_SIZE]; int N,M; int Xmax,Ymax; int xd,yd; void Clear(void) { while(!qu.empty()) { qu.pop(); } } void BFS(void) { int x,y; for(x=0; x<Xmax+1; x++) { for(y=0; y<Ymax+1; y++) { dist[x][y]=INF; } } State pn; pn.x=0; pn.y=0; pn.c=0; dist[0][0]=0; qu.push(pn); while(!qu.empty()) { pn=qu.top(); qu.pop(); x=pn.x; y=pn.y; if(x==xd && y==yd) { return; } // 上 if(y+1 <= Ymax && dist[x][y+1]> dist[x][y]+vE[x][y+1]) { dist[x][y+1]=dist[x][y]+vE[x][y+1]; pn.x=x; pn.y=y+1; pn.c=dist[x][y+1]; qu.push(pn); } // 右 if(x+1 <=Xmax && dist[x+1][y]>dist[x][y]+hE[x+1][y]) { dist[x+1][y]=dist[x][y]+hE[x+1][y]; pn.x=x+1; pn.y=y; pn.c=dist[x+1][y]; qu.push(pn); } // 下 if(y-1 >=0 && dist[x][y-1]> dist[x][y]+vE[x][y]) { dist[x][y-1]=dist[x][y]+vE[x][y]; pn.x=x; pn.y=y-1; pn.c=dist[x][y-1]; qu.push(pn); } // 左 if(x-1 >=0 && dist[x-1][y]>dist[x][y]+hE[x][y]) { dist[x-1][y]=dist[x][y]+hE[x][y]; pn.x=x-1; pn.y=y; pn.c=dist[x-1][y]; qu.push(pn); } } dist[xd][yd]=-1; } int main(void) { int i,j; int x,y,d,t; x=INF; double ex,ec; while(cin>>N>>M) { if(N==-1 && M==-1) break; memset(vE,0,sizeof(vE)); memset(hE,0,sizeof(hE)); Xmax=0; Ymax=0; for(i=0; i<N; i++) { cin>>x>>y>>d>>t; if(d==0) { for(j=0; j<t; j++) { vE[x+j][y]=INF; } Xmax=MAX(x+t,Xmax); Ymax=MAX(y,Ymax); } else { for(j=0; j<t; j++) { hE[x][y+j]=INF; } Xmax=MAX(x,Xmax); Ymax=MAX(y+t,Ymax); } } for(i=0; i<M; i++) { cin>>x>>y>>d; if(d==0) { vE[x][y]=1; } else { hE[x][y]=1; } } cin>>ex>>ec; if(ex>Xmax || ec>Ymax) { cout<<"0"<<endl; } else { xd=int(ex); yd=int(ec); BFS(); cout<<dist[xd][yd]<<endl; Clear(); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator