【面试笔试算法】Program 5 : 推箱子 (网易游戏笔试题)
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
推箱子是一款经典的益智游戏。如图所示，在黑色方块标记不可通行区域中有一个红色方框标识箱子位置，在绿色圆圈表示玩家位置的周围分布着带有小点的方块标记目标位置。
规定以下规则：
1、一局游戏中只会有一个箱子，一个玩家和一个目标点。
2、通过方向键控制玩家移动。
3、图中的灰色格子代表墙壁，玩家与箱子都不能通过。
当一个箱子被推向墙壁时（即难以从其靠近墙的一面将其推出），由于玩家无法接近并推动靠墙的一面（即所谓的"被拉"状态），因此该箱体只能以"受外力作用而发生位移"的方式进行移动（即所谓的"被推"状态）。然而，在这种情况下（即当一个人将一个物体推向墙后），如果沿着墙面两侧没有阻碍物（即两个不同方向均为空旷），则可以在两个不同的方向上推动物体（即实现双重位移）。一旦物体位于房间角落处（即处于封闭状态），则无法进一步推动它。
5、由于游戏机制限制的原因，在此场景中玩家无法离开此场景范围。推动箱子接近游戏边界时，请注意前方可能会有阻挡物阻挡您的路径；持续点击控制面板上的‘向前’按钮将会导致您与箱子一起朝着当前界面中心区域移动；当前方出现阻挡物时（如墙壁），系统将阻止您进一步前行；然而所有这些操作都被视为合法行为并会被系统正确记录
当箱子抵达目标位置时，则将无法继续移动；然而，在此时刻段内玩家仍可自由活动于场景中。若持续施加推力作用于该物体，则会使得双方均停留在同一位置而不发生位移。
请设计一种方向键点击方案，并通过分析以下布局来判定这种方案是否能使箱子最终停在目标点上。其中，在表示可用区域的方格中，请用0标记空白格子，在不可通行的区域中使用4标记，在玩家所在位置用1标记，在需要推动的箱子位置用3标记，在目标点位置用2标记。
输入
在第一行中存在三个整数值N、M和S。其中N是一个大于零且不超过一百的整数代表网格的宽度；M也是一个大于零且不超过一百的整数代表网格的高度；而S则是一个介于零到两百之间的整数表示测试点的数量。
接下来的M行，每行都会有N个字符，描述当前的盘面。
在接下来的S行中，默认情况下会生成多个测试点。每个测试点对应一行数据，在每一行中首先会给出一个整数T（其中T满足条件：即大于零且小于等于1万）。随后会给出一个空格接着给出T个由小写字母组成且仅包含d、u、l和r四个字母的字符串序列。这些字符串序列仅包含四个特定的小写字母并分别对应不同的方向键操作：d表示按动向下键方向键；u表示按动向上键方向键；l表示按动向左键方向键；r表示按动向右键方向键
输出
针对每一个测试点，请判断最终箱子的位置是否与目标坐标一致？如果匹配成功，请返回YES；否则请返回NO。
样例输入
样例输出
YES
YES
NO
代码：
#include "stdafx.h"
#include <string>
#include <stdio.h>
#include <iostream>
using namespace std;
char Board[ 100][100 ]; // 棋盘
char Boardbak[100][100 ];
int main()
{
int n, m , s;
string temp (100, '0');
int player_x = 0 , player_y = 0;
int player_x_bak = 0 , player_y_bak = 0;
bool havaPlayer = false ;
cin >> n >> m >> s;
for (int x = 0; x < m; ++x)
{
cin >> temp;
for ( int y = 0 ; y < n; ++y )
{
if (! havaPlayer && temp [y] == '1')
{
player_x_bak = x;
player_y_bak = y;
havaPlayer = true ;
}
Boardbak [x][ y] = temp [y];
}
}
while (s--)
{
bool isSuccess = false;
int count = 0;
string path (10000, '0');
cin >> count >> path;
//初始化棋盘
for ( int i = 0 ; i < m; ++i )
{
for ( int j = 0 ; j < n; ++j )
{
Board [i][ j] = Boardbak [i][ j];
}
}
//初始化玩家位置
player_x = player_x_bak;
player_y = player_y_bak;
for ( int z = 0 ; z < count;++z )
{
if ( path[z ] == 'd' )//向下
{
if ( player_x + 2 < m) // 判断下面没有越界
{
if (! isSuccess && Board [player_x + 1][ player_y] == '3')// 判断下面有箱子
{
if ( Board[player_x + 2 ][player_y] == '0')// 判断箱子下面是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x + 1][ player_y] = '1' ;
Board [player_x + 2][ player_y] = '3' ;
//更新玩家位置
player_x = player_x + 1;
}
else if (Board[player_x + 2 ][player_y] == '2') //箱子下面是目标点
{
isSuccess = true ;
}
}
else // 判断没有箱子，就只有玩家动
{
if ( Board[player_x + 1 ][player_y] == '0')// 玩家下面是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x + 1][ player_y] = '1' ;
//更新玩家位置
player_x = player_x + 1;
}
}
}
else
{
if ( Board[player_x + 1 ][player_y] == '0') //下面越界，玩家下面是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x + 1][ player_y] = '1' ;
//更新玩家位置
player_x = player_x + 1;
}
}
}
else if (path[z ] == 'u' )//向上
{
if ( player_x - 2 >=0) // 判断上面没有越界
{
if (! isSuccess && Board [player_x - 1][ player_y] == '3')// 判断上面有箱子
{
if ( Board[player_x - 2 ][player_y] == '0')// 判断箱子上面是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x - 1][ player_y] = '1' ;
Board [player_x - 2][ player_y] = '3' ;
//更新玩家位置
player_x = player_x - 1;
}
else if (Board[player_x - 2 ][player_y] == '2') //箱子上面是目标点
{
isSuccess = true ;
}
}
else // 判断没有箱子，就只有玩家动
{
if ( Board[player_x - 1 ][player_y] == '0')// 玩家上面空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x - 1][ player_y] = '1' ;
//更新玩家位置
player_x = player_x - 1;
}
}
}
else
{
if ( Board[player_x - 1 ][player_y] == '0') //上面越界，玩家上面是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x - 1][ player_y] = '1' ;
//更新玩家位置
player_x = player_x - 1;
}
}
}
else if (path[z ] == 'l' )//左
{
if ( player_y - 2 >= 0 ) // 判断左边没有越界
{
if (! isSuccess && Board [player_x][player_y -1 ] == '3')// 判断左边有箱子
{
if ( Board[player_x ][player_y - 2] == '0') //判断箱子左边是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x][player_y - 1] = '1' ;
Board [player_x][player_y - 2] = '3' ;
//更新玩家位置
player_y = player_y - 1;
}
else if (Board[player_x ][player_y - 2] == '2') //箱子左边是目标点
{
isSuccess = true ;
}
}
else // 判断没有箱子，就只有玩家动
{
if ( Board[player_x ][player_y - 1] == '0') //玩家左边是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x][player_y -1 ] = '1' ;
//更新玩家位置
player_y = player_y - 1;
}
}
}
else
{
if ( Board[player_x ][player_y - 1] == '0') //左边越界，玩家左边是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x][player_y - 1] = '1' ;
//更新玩家位置
player_y = player_y - 1;
}
}
}
else if (path[z ] == 'r' )//向右
{
if ( player_y + 2 < n) // 判断右边没有越界
{
if (! isSuccess && Board [player_x][player_y + 1] == '3')// 判断右边有箱子
{
if ( Board[player_x ][player_y + 2] == '0') //判断箱子右边是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x][player_y + 1] = '1' ;
Board [player_x][player_y + 2] = '3' ;
//更新玩家位置
player_y = player_y + 1;
}
else if (Board[player_x ][player_y + 2] == '2') //箱子右边是目标点
{
isSuccess = true ;
}
}
else // 判断没有箱子，就只有玩家动
{
if ( Board[player_x ][player_y + 1] == '0') //玩家右边是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x][player_y + 1] = '1' ;
//更新玩家位置
player_y = player_y + 1;
}
}
}
else
{
if ( Board[player_x ][player_y + 1] == '0') //右边越界，玩家右边是空格
{
//更新棋盘
Board [player_x][player_y] = '0' ;
Board [player_x][player_y + 1] = '1' ;
//更新玩家位置
player_y = player_y + 1;
}
}
}
}
if ( isSuccess)
{
cout << "YES" << endl;
}
else
cout << "NO" << endl;
}
return 0;
}
cpp
