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

单向BFS轻松水过,轻松<100ms,最好47ms!

Posted by wtl666wtl at 2016-02-26 13:13:32 on Problem 1915
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
int L,x,xx,y,yy,n,m,k,z,q[90001][2],d[305][305],fx[8][2]= {{1,2},{-1,2},{1,-2},{-1,-2},{-2,1},{2,1},{-2,-1},{2,-1}};
bool f[305][305];
void gao (int x,int y)
{
	int h=0,t=1;
	q[1][1]=x;
	q[1][2]=y;
	f[x][y]=1;
	d[x][y]=0;
	while(h<t) {
		h++;
		for (int i=0; i<=7; i++) {
			int x1=q[h][1]+fx[i][0],y1=q[h][2]+fx[i][1];
			if(x1>=0&&x1<L&&y1>=0&&y1<L&&f[x1][y1]==0) {
				f[x1][y1]=1;
				t++;
				q[t][1]=x1;
				q[t][2]=y1;
				d[x1][y1]=d[q[h][1]][q[h][2]]+1;
			}
		}
		if(f[xx][yy]==1)return;
	}
}
int main ()
{
	scanf("%d",&n);
	for (int i=1; i<=n; i++) {
		scanf("%d",&L);
		scanf("%d%d",&x,&y);
		scanf("%d%d",&xx,&yy);
		memset(f,0,sizeof(f));
		memset(d,0,sizeof(d));
		gao(x,y);
		printf("%d\n",d[xx][yy]);
	}
	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