本文共 3489 字，大约阅读时间需要 11 分钟。
/*1044.独轮车
时限：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>
using namespace std;
queue<int>x ;//横坐标队列
queue<int>y ;//纵坐标队列
queue<int>color ;//颜色队列
queue<int>dire ;//方向队列
int x1 , y1 , x2 , y2 ;//起点和终点的坐标
int color1 , dire1 ;//起始方向和颜色
int color2 ;//终点的颜色
char a , b, c ;//起点的颜色、方向和重点的颜色
char map[21][21] = {0} ; //地图
int map1[21][21][5][4] = {0} ;//每一个位置具有四个状态 横坐标、纵坐标、方向、颜色 计算时间
//！！！！！！一个找了两天的bug 左下右上的数组和dire1的数据对应 dire1必须是西南东北
int dr[4] = {0 ,1 ,0 ,-1 } ;//左下右上
int dc[4] = {-1 ,0 ,1 ,0} ;
int x0 , y0 , row , col , color0 , dire0 ;
//x0 ，y0 ，color0，dire0是四个队列的队首元素 row1，col1是走一格后的位置
void input() ;//输入数据
void init() ;//对数据初始化把字母变为数字好处理
int bfs() ; //广搜找答案
void move() ;//变换到新状态
int main()
{
input() ;//输入数据
bfs() ;//找答案
}
void input()
{
int i, j ;
cin >> x1 >> y1 >> a >> b >> x2 >> y2 >> c ;//输入数据
for(i = 1 ; i <= 20 ; i++)
{
for(j = 1 ; j <= 20 ; j++)
{
cin >> map[i][j] ;
}
}
init() ; //初始化
}
int bfs()
{
int i ;
while(!x.empty())
{
x0 = x.front() ;//访问横、纵坐标、方向、颜色队首元素并使其出队
x.pop() ;
y0 = y.front() ;
y.pop() ;
dire0 = dire.front() ;
dire.pop() ;
color0 = color.front() ;
color.pop() ;
move() ; //变换到新状态
for(i = 0 ; i <= 3 ; i++)//达到目标状态就输出 因为题中方向位置所以要for循环一下
{
if(map1[x2][y2][color2][i] != 0)//走到了目标状态
{
cout << map1[x2][y2][color2][i] << endl ;
return 0 ;
}
}
}
return -1 ; //未找到答案返回 -1
}
void init() //R-红、Y-黄、B-蓝、W-白、G-绿
{
if(a == 'R')
{
color1 = 0 ;
}
if(a == 'Y')
{
color1 = 1 ;
}
if(a == 'B')
{
color1 = 2 ;
}
if(a == 'W')
{
color1 = 3 ;
}
if(a == 'G')
{
color1 = 4 ;
}
if(b == 'W')
{
dire1 = 0 ;
}
if(b == 'S')
{
dire1 = 1 ;
}
if(b == 'E')
{
dire1 = 2 ;
}
if(b == 'N')
{
dire1 = 3 ;
}
if(c == 'R')
{
color2 = 0 ;
}
if(c == 'Y')
{
color2 = 1 ;
}
if(c == 'B')
{
color2 = 2 ;
}
if(c == 'W')
{
color2 = 3 ;
}
if(c == 'G')
{
color2 = 4 ;
}
x.push(x1) ;//起点的横、纵坐标、颜色、方向入队
y.push(y1) ;
color.push(color1) ;
dire.push(dire1) ;
map1[x1][y1][color1][dire1] = 0 ;//起始位置的累计时间为0
}
void move()
{
//变换颜色和方向 坐标直接加减 颜色和方向取模循环
//元素入队
//步数+1
row = x0 + dr[dire0] ;
col = y0 + dc[dire0] ;
if(map[row][col] == '.' && map1[row][col][(color0+1)%5][dire0] == 0)//走一步费一个单位时间
{
map1[row][col][(color0+1)%5][dire0] = map1[x0][y0][color0][dire0] + 1 ;
x.push(row);
y.push(col);
color.push((color0+1)%5);
dire.push(dire0);
}
if(map1[x0][y0][color0][(dire0+1)%4] == 0)//直接转换方向
{
map1[x0][y0][color0][(dire0+1)%4] = map1[x0][y0][color0][dire0] + 1 ;
x.push(x0);
y.push(y0);
color.push(color0);
dire.push((dire0+1)%4);
}
if(map1[x0][y0][color0][(dire0-1+4)%4] == 0)//直接转换方向
{
map1[x0][y0][color0][(dire0-1+4)%4] = map1[x0][y0][color0][dire0] + 1 ;
x.push(x0);
y.push(y0);
color.push(color0);
dire.push((dire0-1+4)%4);
}
}
发表评论
最新留言
关于作者
