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 1A

Posted by cedricgsh55 at 2019-03-21 15:52:49 on Problem 2251
/* 三维的走迷宫问题 */
/*
  超时的注意用一个vis数组标记一下已经访问节点,可以缩短搜索队列的长度
*/
#include<iostream>
#include<queue>
using namespace std;
char map[35][35][35];
int vis[35][35][35];
int change[6][3]={1, 0, 0,-1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0,-1};
struct node
{
	int x, y, z;
	int step;
};
int l, r, c;
int sl,sx, sy;
int ex, ey;
int bfs(int th, int tx, int ty)
{
	memset(vis, 0, sizeof(vis));
	node a;
	a.z = th;
	a.x = tx;
	a.y = ty;
	a.step = 0;
	vis[a.z][a.x][a.y] = 1;
	queue<node> arr;
	arr.push(a);
	while (arr.size())
	{
		node t = arr.front();
		arr.pop();
		//cout <<t.z<<"  "<<t.x<<"  "<<t.y<<" "<< map[t.z][t.x][t.y] << endl;
		if (map[t.z][t.x][t.y] == 'E')
		{
			return t.step;
			
		}
		for (int i = 0; i < 6; i++)
		{
			node s;
			s.z = t.z + change[i][0];
			s.x = t.x + change[i][1];
			s.y = t.y + change[i][2];
			if (s.z >= 1 && s.z <= l&&s.x >= 1 && s.x <= r&&s.y >= 1 && s.y <= c&&!vis[s.z][s.x][s.y] && map[s.z][s.x][s.y] != '#')
			{
				s.step = t.step + 1;
				vis[s.z][s.x][s.y] = 1;
				arr.push(s);
			}
		}
	}
	return -1;
}
int main()
{
	while (cin >> l >> r >> c, l + r + c)
	{
		for (int i = 1; i <= l; i++)
			for (int j = 1; j <= r; j++)
				for (int k = 1; k <= c; k++)
				{
					cin >> map[i][j][k];
					if (map[i][j][k] == 'S')
					{
						sl = i; sx = j; sy = k;
					}
				}
		int res=bfs(sl, sx, sy);
		if (res == -1)
			cout << "Trapped!" << endl;
		else
			cout << "Escaped in " << res << " minute(s)." << endl;
	}
	system("pause");
	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