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 zhouzp15 at 2017-01-24 23:44:12 on Problem 3083
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;

const int N = 40 + 5;
int size_x, size_y;
int st_x, st_y, end_x, end_y;
char map[N][N];
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { -1, 0, 1, 0 };
int queue[N * N], step[N][N];
bool pd[N][N];

#define rotate(p,dir) ((p + dir + 4) % 4)
int go(int dir) // -1-left, 1-right
{
	int p, cnt = 0; 
	if (st_x - 1 >= 0 && st_x - 1 < size_x && map[st_x - 1][st_y] == '#')
		p = (st_y == 0 ? 2 : 0);
	else p = (st_x == 0 ? 1 : 3);
	
	int x = st_x, y = st_y;
	while (x != end_x || y != end_y)
	{
		while (map[y + dy[p]][x + dx[p]] == '#') 
			p = rotate(p, -dir);
		
		x += dx[p]; y += dy[p]; cnt++;
		if (map[y + dy[rotate(p, dir)]][x + dx[rotate(p, dir)]] != '#')
			p = rotate(p, dir);
	}
	return cnt + 1;
}

#define ok(x,y) (x >= 0 && x < size_x && y >= 0 && y < size_y)
int bfs()
{
	int l = 0, r = 0;
	memset(pd, false, sizeof(pd));
	
	step[st_x][st_y] = 1;
	queue[r++] = st_x * size_x + st_y;
	while (l < r)
	{
		int p = queue[l++];
		for (int i = 0; i < 4; i++) 
		{
			int x = p / size_x, y = p % size_x;
			int x1 = x + dx[i], y1 = y + dy[i];
			if (!pd[x1][y1] && ok(x1, y1) && map[y1][x1] != '#')
			{
				queue[r++] = x1 * size_x + y1; pd[x1][y1] = true;
				step[x1][y1] = step[x][y] + 1;
				if (x1 == end_x && y1 == end_y) 
					return step[x1][y1];
			}
		}
	}
	return -1;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d\n", &size_x, &size_y);
		for (int i = 0; i < size_y; i++) 
		{
			gets(map[i]);
			for (int j = 0; j < size_x; j++) 
				if (map[i][j] == 'S') st_x = j, st_y = i;
				else if (map[i][j] == 'E') end_x = j, end_y = i;
		}
		printf("%d %d %d\n", go(-1), go(1), bfs());
	}
	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