hihoCoder_推箱子
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-04-29 08:40:20 閱讀次數(shù)：2678次
1.題目
題目1 : 推箱子
時(shí)間限制:10000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
-
描寫(xiě)
推箱子是1款經(jīng)典游戲。如圖所示，灰色格子代表不能通過(guò)區(qū)域，藍(lán)色方格是箱子，黑色圓形代表玩家，含有圓點(diǎn)的格子代表目標(biāo)點(diǎn)。
規(guī)定以下規(guī)則：
1、1局游戲中只會(huì)有1個(gè)箱子，1個(gè)玩家和1個(gè)目標(biāo)點(diǎn)。
2、通過(guò)方向鍵控制玩家移動(dòng)。
3、圖中的灰色格子代表墻壁，玩家與箱子都不能通過(guò)。
4、推到墻壁的箱子，就沒(méi)法再將箱子推離墻壁，由于玩家沒(méi)法到達(dá)箱子靠墻壁的1側(cè)去推箱子。也就是說(shuō)箱子只能以“被推”的方式被移動(dòng)，不是以“被拉”的方式被移動(dòng)。但如果玩家將箱子推至墻壁后，垂直墻壁的兩側(cè)沒(méi)有阻礙物，則玩家可以朝這兩個(gè)不同的方向推移箱子。如果箱子進(jìn)入角落，就沒(méi)有辦法再推動(dòng)這個(gè)箱子了。
5、玩家是不能走出場(chǎng)景的。玩家推著箱子到達(dá)場(chǎng)景邊沿，如果繼續(xù)點(diǎn)擊使玩家和箱子向墻壁前進(jìn)的方向鍵，箱子和人都會(huì)保持不動(dòng)。玩家的前進(jìn)方向上如果有墻壁，也是不能前進(jìn)的。但是這些點(diǎn)擊都視為公道的輸入。
6、箱子1旦到達(dá)目標(biāo)點(diǎn)，就不能再移動(dòng)了。但這時(shí)候，玩家依然可以在場(chǎng)景內(nèi)自由行動(dòng)。如果繼續(xù)嘗試推箱子，那末玩家將會(huì)和箱子1起保持在原地不動(dòng)。
現(xiàn)在，給出1種方向鍵的點(diǎn)擊方案，請(qǐng)判斷，這類方案是不是能使箱子終究停在目標(biāo)點(diǎn)上。為了方便表示，我們以0代表空白格子，以4代表不能通過(guò)區(qū)域，以1代表玩家，以3代表箱子，以2代表目標(biāo)點(diǎn)。
輸入
第1行數(shù)據(jù)包括3個(gè)整數(shù)，N，M，S。其中，N(0 < N <= 100)代表格子的寬度，M(0 < M <= 100)代表格子的高度，S(0 < S <= 200)代表測(cè)試點(diǎn)的個(gè)數(shù)。
接下來(lái)的M行，每行都會(huì)有N個(gè)字符，描寫(xiě)當(dāng)前的盤面。
接下來(lái)的S行，每行都代表1個(gè)測(cè)試點(diǎn)。每行都以1個(gè)整數(shù)T(0 < T <= 10000)開(kāi)頭，接下來(lái)是1個(gè)空格和T個(gè)字符。這T個(gè)字符僅由d，u，l，r這4個(gè)字母組成，分別代表了敲擊向下，向上，向左，向右的方向鍵。
輸出
對(duì)每一個(gè)測(cè)試點(diǎn)，輸出最后箱子是不是在目標(biāo)點(diǎn)上。如果是，輸出YES，如果不是，則輸出NO。
-
-
- 樣例輸入
-
5 4 3
00000
13000
00200
00000
4 rurd
6 urdldr
6 rrrurd
- 樣例輸出
-
YES
YES
NO
2.解題技能
這道題主要就是斟酌各種邊界條件的問(wèn)題，并沒(méi)有包括過(guò)量的算法。
3.實(shí)現(xiàn)代碼
#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.體會(huì)
這道題全在斟酌邊界條件和寫(xiě)代碼速度上面了，并沒(méi)有太多需要思考的算法問(wèn)題。
版權(quán)所有，歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處，謝謝
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
