【NOJ1044】【算法实验三】【BFS_分支限界】独轮车

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'表示建筑物，'.'表示路.

输出

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

第二版代码： 

#include <iostream>
#include <queue>

using namespace std;

//注：题中坐标从【1，1】开始
//但本代码中坐标从【0，0】开始
//因此对sx，sy，tx，ty都做了-1处理

/*****数据输入所需变量*****/
int sx,sy;
char sc,sd;

int tx,ty;
char tc;

char maze[20][20];
/***************************/

/******广搜所用数据结构********/
struct node
{
    int x;
    int y;
    int color;  //颜色，0-R-红，1-Y-黄，2-B-蓝，3-W-白，4-G-绿
    int dire;   //方向：0-E-东，1-S-南，2-W-西，3-N-北
};

node start,target;

queue <node> q1;

int used[20][20][5][4];
int time[20][20][5][4];

int walk[4][2]= //向前走一格的坐标变化
{
    0, +1,  //0-E-东
    +1, 0,  //1-S-南
    0, -1,  //2-W-西
    -1, 0   //3-N-北
};
/******************************/

/******函数声明********/
//输入数据函数
void input();

//初始化函数
void init();

//将代表颜色的字母转化为数字
int colorToInt(char c);

//将代表方向的字母转化为数字
int direToInt(char d);

//算法执行函数
int bfs();

//返回移动后的新节点（不保证有效）
node moveto(node now, int i);

//判断节点有效性
bool effective(node next);

//判断是否到达目标节点
bool isTarget(node next);
/***********************/

int main()
{
    input();
    init();
    cout<<bfs()<<endl;
    return 0;
}

//输入数据函数
void input()
{
    cin>>sx>>sy>>sc>>sd;
    cin.get();
    cin>>tx>>ty>>tc;
    cin.get();  //吃掉回车

    for(int i=0; i<20; i++)
    {
        for(int j=0; j<20; j++)
        {
            maze[i][j]=cin.get();
        }
        cin.get();  //吃掉回车
    }
}

//初始化函数
//因本题只有一个判例，而且本人巨懒
//故不初始化队列、判重数组、步数数组
void init()
{
    //设置初始节点
    start.x=sx-1;
    start.y=sy-1;
    start.color=colorToInt(sc);
    start.dire=direToInt(sd);

    //标记初始节点并入队
    used[start.x][start.y][start.color][start.dire]=1;
    q1.push(start);

    //设置目标节点
    target.x=tx-1;
    target.y=ty-1;
    target.color=colorToInt(tc);
}

//将代表颜色和方向的字母转化为数字
int colorToInt(char c)
{
    switch(c)
    {
        //关于颜色的转换
        case'R':return 0;
        case'Y':return 1;
        case'B':return 2;
        case'W':return 3;
        case'G':return 4;
    }
    return -1;
}

//将代表方向的字母转化为数字
int direToInt(char d)
{
    switch(d)
    {
        //关于方向的转换
        case'E':return 0;
        case'S':return 1;
        case'W':return 2;
        case'N':return 3;
    }
    return -1;
}

//算法执行函数
int bfs()
{
    node now,next;
    while(!q1.empty())
    {
        now=q1.front();
        q1.pop();

        for(int i=0; i<3; i++)  //0==向前走，1==原地左转，2==原地右转
        {
            next=moveto(now, i);    //移动后的新节点next
            if(effective(next))     //若有效
            {
                used[next.x][next.y][next.color][next.dire]=1;
                time[next.x][next.y][next.color][next.dire]=
                    1+time[now.x][now.y][now.color][now.dire];

                if(isTarget(next))  //判断是否到达目标
                {
                    return time[next.x][next.y][next.color][next.dire];
                }
                else    //若未到达目标则入队
                {
                    q1.push(next);
                }
            }
        }
    }
    return -1;
}

//返回移动后的新节点（不保证有效）
node moveto(node now, int i)
{
    node next;

    if(i==0)    //向前走一格
    {
        next.x=now.x+walk[now.dire][0];
        next.y=now.y+walk[now.dire][1];
        next.color=(now.color+1)%5;
        next.dire=now.dire;
    }
    else    //原地转向
    {
        next.x=now.x;
        next.y=now.y;
        next.color=now.color;
        if(i==1)    //左转
        {
            next.dire=(now.dire+4-1)%4;
        }
        else        //右转
        {
            next.dire=(now.dire+1)%4;
        }
    }
    return next;
}

//判断节点有效性
//无效条件：越界、撞墙、重复
bool effective(node next)
{
    if(next.x>=0&&next.x<20&&next.y>=0&&next.y<20)  //不越界
    {
        if(maze[next.x][next.y]!='X')   //不撞墙
        {
            if(!used[next.x][next.y][next.color][next.dire])    //不重复
            {
                return true;
            }
        }
    }
    return false;
}

//判断是否到达目标节点
bool isTarget(node next)
{
    if(next.x==target.x&&next.y==target.y&&next.color==target.color)
    {
        return true;
    }
    else
    {
        return false;
    }
}

【10月21日后记】

1.第二次做的时候，代码写的很顺利，但是，因为，过于自负，少看了一个条件（原地转向时该死的车轮不变色啊啊啊），直接导致dubug时间成倍延长QAAAAAAAQ，下次一定要认真审题！！！

2.感觉写bfs已经形成套路了，如果看我bfs的前几篇文章里的代码就能看出来，用的数据结构，变量，函数，判断条件其实就那么几个，bfs函数里的套路都是一样的，重构后的第二版代码比第一版少了一百来行，emmmmm，现在应该不算是又臭又长的代码了叭。

3.不说了去吃饭了我好饿。

4.如果csdn里的代码也可以像在cb里那样折叠就好了，像input，init这种函数没什么看的必要，但因为出现顺序还是要放在bfs函数前面，影响关键信息阅读。

【10月7日后记】

1.第一次感觉代码写的心力交瘁……累skr人……大概也不会有人看这么又臭又长的代码叭……