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。。。都不知道在说什么,然后写的程序就过了= =这尼玛太假了

Posted by xmu_ch at 2013-03-10 00:26:14 on Problem 1915
#include<iostream>
#include<queue>
using namespace std;
#include<memory.h>
#define maxn 1000
int end_x,end_y;
int l;

struct node
{
	int x,y;
	int step;
};

bool vis[maxn][maxn];

int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};

int bfs(int x,int y)
{
	int d;
	memset(vis,false,sizeof(vis));
	queue<node>q;
	node cur,next;
	cur.x = x;
	cur.y = y;
	cur.step = 0;
	q.push(cur);
	vis[x][y] = true;
	while(!q.empty())
	{
		cur = q.front();
		q.pop();
		if(x == end_x && y == end_y)
			return cur.step;
		for(d = 0; d < 8;d++)
		{
			next.x = cur.x + dir[d][0];
			next.y = cur.y + dir[d][1];
			if(next.x >= 0 && next.y >= 0 && next.x <= l-1 && next.y <= l-1 && !vis[next.x][next.y])
			{
				next.step = cur.step + 1;
				if(end_x == next.x && end_y == next.y)
					return next.step;
				vis[next.x][next.y] = true;
				q.push(next);
			}
		}
	}
	return -1;
}

int main()
{
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	int n;
	int step;
	int start_x,start_y;
	cin >> n;
	for(int i = 0; i < n;i++)
	{
		cin >> l;
		cin >> start_x >> start_y;
		cin >> end_x >> end_y;
		step = bfs(start_x,start_y);
		cout << step << endl;
	}
	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