独轮车

　

独轮车

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

独轮车的轮子上有红、黄、蓝、白、绿（依顺时针序）5种颜色，在一个如下图所示的20*20的迷宫内每走一个格子，轮子上的颜色变化一次。独轮车只能向前推或在原地转向。每走一格或原地转向90度均消耗一个单位时间。现给定一个起点（S）和一个终点（T），求独轮车以轮子上的指定颜色到达终点所需的最短时间。

输入

本题包含一个测例。测例中分别用一个大写字母表示方向和轮子的颜色，其对应关系为：E-东、S-南、W-西、N-北；R-红、Y-黄、B-蓝、W-白、G-绿。在测试数据的第一行有以空格分隔的两个整数和两个大写字母，分别表示起点的坐标S（x,y）、轮子的颜色和开始的方向，第二行有以空格分隔的两个整数和一个大写字母，表示终点的坐标T（x,y）和到达终点时轮子的颜色，从第三行开始的20行每行内包含20个字符，表示迷宫的状态。其中'X'表示建筑物，'.'表示路.

输出

在单独的一行内输出一个整数，即满足题目要求的最短时间。

输入样例

3 4 R N

15 17 Y

XXXXXXXXXXXXXXXXXXXX

X.X...XXXXXX......XX

X.X.X.....X..XXXX..X

X.XXXXXXX.XXXXXXXX.X

X.X.XX....X........X

X...XXXXX.X.XX.X.XXX

X.X.XX....X.X..X.X.X

X.X.X..XX...XXXX.XXX

X.X.XX.XX.X....X.X.X

X.X....XX.X.XX.X.X.X

X.X.X.XXXXX.XX.X.XXX

X.X.X.XXXXX....X...X

X.X.......X.XX...X.X

X.XXX.XXX.X.XXXXXXXX

X.....XX.......X...X

XXXXX....X.XXXXXXX.X

X..XXXXXXX.XXX.XXX.X

X.XX...........X...X

X..X.XXXX.XXXX...XXX

XXXXXXXXXXXXXXXXXXXX

输出样例

56

#include<iOStream>
#include<queue>
#include<cstdlib>
#include <cstdio>
#include<cstring> 

using namespace std;

char maze[20][20];
int  sx, sy, fx, fy, sc, sd, fc; 
char c1, c2, d; 
int dir[4][2]= {{0,1}, {1,0}, {0,-1}, {-1,0}};
int vis[20][20][5][4]={0};
int t[20][20][5][4];

int bfs();
int direction(char ch);
int color(char m);

struct Node
{
	int x;
	int y;
	int color;
	int direct;
	int time;
};

int direction(char ch)
{
	if(ch == 'E')
	{
		return 0;
	} 
	if(ch == 'S')
	{
		return 1;
	}
	if(ch == 'W')
	{
		return 2;
	}
	if(ch == 'N')
	{
		return 3;
	}
} 

int color(char m)
{
	if(m == 'R')
	{
		return 0;
	}
	if(m == 'Y')
	{
		return 1;
	}
	if(m == 'B')
	{
		return 2;
	}
	if(m == 'W')
	{
		return 3;
	}
	if(m == 'G')
	{
		return 4;
	} 
}

int bfs()
{
	int i;
	queue<Node> q1;
	Node now,next;
	now.x = sx-1;
	now.y = sy-1;
	now.color = color(c1);
	now.time = 0;
	now.direct = direction(d);
	q1.push(now);
	vis[now.x][now.y][now.color][now.direct] = 1;
	while(!q1.empty())
	{
		now = q1.front();
		q1.pop();
		for(int i=0;i<3;i++)
		{
			if(i==0)
			{
				next.x = now.x;
				next.y = now.y;
				next.color = now.color;
				next.direct = (now.direct + 1) % 4;
			}
			if(i==1)
			{
				next.x = now.x;
				next.y = now.y;
				next.color = now.color;
				next.direct = (now.direct + 3) % 4;
			}
			if(i==2)
			{
				next.x += dir[now.direct][0];
				next.y += dir[now.direct][1];
				next.color = (now.color + 1) % 5;
				next.direct = now.direct;
			}
			if(next.x==(fx-1)&&next.y == (fy-1)&&next.color==color(c2))
			{
				return (now.time + 1);
			}
			if(next.x >= 0&&next.y >= 0&&next.x < 20&&next.y < 20&& vis[next.x][next.y][next.color][next.direct] == 0&&maze[next.x][next.y] == '.')
			{
				vis[next.x][next.y][next.color][next.direct] = 1;
				next.time = now.time + 1;
				q1.push(next); 
			}  
		}
	}
	return -1;
}

int main() 
{
    int i,j;
    cin >> sx >> sy >> c1 >> d;
    cin >> fx >> fy >> c2;
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            cin >> maze[i][j];
        }
    }
    cout << bfs() << endl;
    getchar();
    return 0;
} 

相关阅读