Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一次 AC 奉献代码

Posted by zihuacs at 2010-08-05 20:21:08 on Problem 2049

#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator