hihoCoder_推箱子
栏目：综合技术时间：2015-04-29 08:40:20
1.题目
题目1 : 推箱子
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
-
描写
推箱子是1款经典游戏。如图所示，灰色格子代表不能通过区域，蓝色方格是箱子，黑色圆形代表玩家，含有圆点的格子代表目标点。
规定以下规则：
1、1局游戏中只会有1个箱子，1个玩家和1个目标点。
2、通过方向键控制玩家移动。
3、图中的灰色格子代表墙壁，玩家与箱子都不能通过。
4、推到墙壁的箱子，就没法再将箱子推离墙壁，由于玩家没法到达箱子靠墙壁的1侧去推箱子。也就是说箱子只能以“被推”的方式被移动，不是以“被拉”的方式被移动。但如果玩家将箱子推至墙壁后，垂直墙壁的两侧没有阻碍物，则玩家可以朝这两个不同的方向推移箱子。如果箱子进入角落，就没有办法再推动这个箱子了。
5、玩家是不能走出场景的。玩家推着箱子到达场景边沿，如果继续点击使玩家和箱子向墙壁前进的方向键，箱子和人都会保持不动。玩家的前进方向上如果有墙壁，也是不能前进的。但是这些点击都视为公道的输入。
6、箱子1旦到达目标点，就不能再移动了。但这时候，玩家依然可以在场景内自由行动。如果继续尝试推箱子，那末玩家将会和箱子1起保持在原地不动。
现在，给出1种方向键的点击方案，请判断，这类方案是不是能使箱子终究停在目标点上。为了方便表示，我们以0代表空白格子，以4代表不能通过区域，以1代表玩家，以3代表箱子，以2代表目标点。
输入
第1行数据包括3个整数，N，M，S。其中，N(0 < N <= 100)代表格子的宽度，M(0 < M <= 100)代表格子的高度，S(0 < S <= 200)代表测试点的个数。
接下来的M行，每行都会有N个字符，描写当前的盘面。
接下来的S行，每行都代表1个测试点。每行都以1个整数T(0 < T <= 10000)开头，接下来是1个空格和T个字符。这T个字符仅由d，u，l，r这4个字母组成，分别代表了敲击向下，向上，向左，向右的方向键。
输出
对每一个测试点，输出最后箱子是不是在目标点上。如果是，输出YES，如果不是，则输出NO。
-
-
- 样例输入
-
5 4 3 00000 13000 00200 00000 4 rurd 6 urdldr 6 rrrurd
- 样例输出
-
YES YES NO
2.解题技能
这道题主要就是斟酌各种边界条件的问题，并没有包括过量的算法。
3.实现代码
#include <iostream>
#include <vector>
using namespace std;
class Box
{
private:
vector<vector<char> > Board;
unsigned char Width;
unsigned char Height;
unsigned char X;
unsigned char Y;
bool IsSucceed;
public:
// constructor
Box(int N, int M);
Box(const Box& Origin);
void BuildBoard();
void MoveUp();
void MoveDown();
void MoveLeft();
void MoveRight();
void Move(const char& SingleMove);
bool Move(const vector<char> &Moves);
void Print();
};
Box::Box(int N, int M) : Board(), Width(N), Height(M), X(255), Y(255), IsSucceed(false)
{
}
Box::Box(const Box& Origin):Board(Origin.Board), Width(Origin.Width),
Height(Origin.Height), X(Origin.X), Y(Origin.Y), IsSucceed(Origin.IsSucceed)
{
}
void Box::BuildBoard()
{
for (int IndexOfRows = 0; IndexOfRows < Height; IndexOfRows++)
{
vector<char> Row;
for (int IndexOfCols = 0; IndexOfCols < Width; IndexOfCols++)
{
char InputChar = 0;
cin >> InputChar;
InputChar = InputChar - '0';
if (InputChar == 1)
{
X = IndexOfCols;
Y = IndexOfRows;
}
Row.push_back(InputChar);
}
Board.push_back(Row);
}
}
void Box::MoveUp()
{
if (Y < 1)
{
return;
}
int NextY = Y - 1;
// The upper is the box in the right point
if (Board[NextY][X] == 5)
{
IsSucceed = true;
return;
}
// The upper is box
if (Board[NextY][X] == 3 )
{
if (Y == 1)
{
return;
}
// the upper of the box is the wall
if (Board[NextY - 1][X] == 4)
{
return;
}
// updating
Board[NextY - 1][X] += 3;
Board[NextY][X] = 1;
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
Y = NextY;
if (Board[NextY - 1][X] == 5)
{
IsSucceed = true;
}
return;
}
// the upper is wall
if (Board[NextY][X] == 4)
{
return;
}
// the upper is zero
if (Board[NextY][X] == 0)
{
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
Board[NextY][X] = 1;
Y = NextY;
return;
}
if (Board[NextY][X] == 2)
{
Board[Y][X] = 0;
Y = NextY;
return;
}
}
void Box::MoveDown()
{
if (Y > (Height - 2))
{
return;
}
int NextY = Y + 1;
// The upper is the box in the right point
if (Board[NextY][X] == 5)
{
IsSucceed = true;
return;
}
// The upper is box
if (Board[NextY][X] == 3 )
{
if (Y == (Height - 2))
{
return;
}
// the upper of the box is the wall
if (Board[NextY + 1][X] == 4)
{
return;
}
// updating
Board[NextY + 1][X] += 3;
Board[NextY][X] = 1;
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
Y = NextY;
if (Board[NextY + 1][X] == 5)
{
IsSucceed = true;
}
return;
}
// the upper is wall
if (Board[NextY][X] == 4)
{
return;
}
// the upper is zero
if (Board[NextY][X] == 0)
{
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
Board[NextY][X] = 1;
Y = NextY;
return;
}
if (Board[NextY][X] == 2)
{
Board[Y][X] = 0;
Y = NextY;
return;
}
}
void Box::MoveLeft()
{
if (X < 1)
{
return;
}
int NextX = X - 1;
// The upper is the box in the right point
if (Board[Y][NextX] == 5)
{
IsSucceed = true;
return;
}
// The upper is box
if (Board[Y][NextX] == 3 )
{
if (X == 1)
{
return;
}
// the upper of the box is the wall
if (Board[Y][NextX - 1] == 4)
{
return;
}
// updating
Board[Y][NextX - 1] += 3;
Board[Y][NextX] = 1;
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
X = NextX;
if (Board[Y][NextX - 1] == 5)
{
IsSucceed = true;
}
return;
}
// the upper is wall
if (Board[Y][NextX] == 4)
{
return;
}
// the upper is zero
if (Board[Y][NextX] == 0)
{
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
Board[Y][NextX] = 1;
X = NextX;
return;
}
if (Board[Y][NextX] == 2)
{
Board[Y][X] = 0;
X = NextX;
return;
}
}
void Box::MoveRight()
{
if (X > (Width - 2))
{
return;
}
int NextX = X + 1;
// The upper is the box in the right point
if (Board[Y][NextX] == 5)
{
IsSucceed = true;
return;
}
// The upper is box
if (Board[Y][NextX] == 3 )
{
if (X == (Width - 2))
{
return;
}
// the upper of the box is the wall
if (Board[Y][NextX + 1] == 4)
{
return;
}
// updating
Board[Y][NextX + 1] += 3;
Board[Y][NextX] = 1;
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
X = NextX;
if (Board[Y][NextX + 1] == 5)
{
IsSucceed = true;
}
return;
}
// the upper is wall
if (Board[Y][NextX] == 4)
{
return;
}
// the upper is zero
if (Board[Y][NextX] == 0)
{
if (Board[Y][X] != 2)
{
Board[Y][X] = 0;
}
Board[Y][NextX] = 1;
X = NextX;
return;
}
if (Board[Y][NextX] == 2)
{
Board[Y][X] = 0;
X = NextX;
return;
}
}
void Box::Move(const char &SingleMove)
{
//Print();
switch(SingleMove)
{
case 'u':
MoveUp();
break;
case 'd':
MoveDown();
break;
case 'l':
MoveLeft();
break;
case 'r':
MoveRight();
break;
default:
break;
}
//cout << "X is " << X << endl;
//cout << "Y is " << Y << endl;
//Print();
}
bool Box::Move(const vector<char> &Moves)
{
const int SIZE = Moves.size();
for (int Index = 0; Index < SIZE; Index++)
{
Move(Moves[Index]);
if (IsSucceed)
{
return true;
}
}
return false;
}
void Box::Print()
{
const int SIZE = Board.size();
for (int RowIndex = 0; RowIndex < SIZE; RowIndex++)
{
vector<char> Row = Board[RowIndex];
int COLS = Row.size();
for (int ColIndex = 0; ColIndex < COLS; ColIndex++)
{
char Tmp = Row[ColIndex] + '0';
cout << Tmp;
}
cout << endl;
}
}
int main()
{
int N = 0, M = 0;
int S = 0;
cin >> N >> M >> S;
Box Box_1(N, M);
Box_1.BuildBoard();
while (S--)
{
Box Box_Tmp(Box_1);
int Number = 0;
vector<char> Moves;
cin >> Number;
while(Number--)
{
char SinlgeMove = '0';
cin >> SinlgeMove;
Moves.push_back(SinlgeMove);
}
if (Box_Tmp.Move(Moves))
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
4.体会
这道题全在斟酌边界条件和写代码速度上面了，并没有太多需要思考的算法问题。
版权所有，欢迎转载，转载请注明出处，谢谢
------分隔线----------------------------
上一篇 数据结构学习――线性表
下一篇 每日一题18：栈
------分隔线----------------------------