网易游戏2016实习生招聘笔试题目--推箱子

[sunstrikes]

题目1 : 推箱子
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
推箱子是一款经典游戏。如图所示，灰色格子代表不能通过区域，蓝色方格是箱子，黑色圆形代表玩家，含有圆点的格子代表目标点。

push.png

规定以下规则：

1、一局游戏中只会有一个箱子，一个玩家和一个目标点。

2、通过方向键控制玩家移动。

3、图中的灰色格子代表墙壁，玩家与箱子都不能通过。

4、推到墙壁的箱子，就无法再将箱子推离墙壁，因为玩家无法到达箱子靠墙壁的一侧去推箱子。也就是说箱子只能以“被推”的方式被移动，不是以“被拉”的方式被移动。但如果玩家将箱子推至墙壁后，垂直墙壁的两侧没有阻碍物，则玩家可以朝这两个不同的方向推移箱子。如果箱子进入角落，就没有办法再推动这个箱子了。

5、玩家是不能走出场景的。玩家推着箱子到达场景边缘，如果继续点击使玩家和箱子向墙壁前进的方向键，箱子和人都会保持不动。玩家的前进方向上如果有墙壁，也是不能前进的。但是这些点击都视为合理的输入。

6、箱子一旦到达目标点，就不能再移动了。但这时，玩家仍然可以在场景内自由行动。如果继续尝试推箱子，那么玩家将会和箱子一起保持在原地不动。

现在，给出一种方向键的点击方案，请判断，这种方案是否能使箱子最终停在目标点上。为了方便表示，我们以0代表空白格子，以4代表不能通过区域，以1代表玩家，以3代表箱子，以2代表目标点。

输入
第一行数据包含三个整数，N，M，S。其中，N(0 < N <= 100)代表格子的宽度，M(0 < M <= 100)代表格子的高度，S(0 < S <= 200)代表测试点的个数。

接下来的M行，每行都会有N个字符，描述当前的盘面。

接下来的S行，每行都代表一个测试点。每行都以一个整数T(0 < T <= 10000)开头，接下来是一个空格和T个字符。这T个字符仅由d，u，l，r这四个字母组成，分别代表了敲击向下，向上，向左，向右的方向键。

输出
对于每个测试点，输出最后箱子是否在目标点上。如果是，输出YES，如果不是，则输出NO。

样例输入
5 4 3
00000
13000
00200
00000
4 rurd
6 urdldr
6 rrrurd
样例输出
YES
YES
NO

模拟...

#include <iostream>
#include"math.h"
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<numeric>
#include<set>
#include<map>
#include<cstring>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
struct point {
    int x, y;
};

point push(char x) {
    point a;
    switch (x) {
    case 'r': {a.x = 0; a.y = 1; break; }
    case 'l': {a.x = 0; a.y = -1; break; }
    case 'u': {a.x = -1; a.y = 0; break; }
    case 'd': {a.x = 1; a.y = 0; break; }
    }
    return a;
}
int n, m, s;
char d[105][105];
char a[105][105];
bool judge(int way, string &s) {
    bool flag = false;
    int x1, y1;
    int x2, y2;
    int x3, y3;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = a[i][j];
            if (d[i][j] == '1') {
                x1 = i; y1 = j;
            }
        }
    }
    for (int i = 0; i < s.size(); i++) {
        point o = push(s[i]);
        x2 = o.x + x1;
        y2 = o.y + y1;
        if (d[x2][y2] == '0') {
            d[x2][y2] = '1';
            d[x1][y1] = '0';
            x1 = x2; y1 = y2;
            continue;
        }
        else if (x2 <= 0 || x2>m || y2 <= 0 || y2>n || d[x2][y2] == '4') {
            continue;
        }
        else if (d[x2][y2] == '3') {
            x3 = x2 + o.x;
            y3 = y2 + o.y;
            if (d[x3][y3] == '0') {
                d[x3][y3] = '3';
                d[x2][y2] = '1';
                d[x1][y1] = '0';
                x1 = x2; y1 = y2;
            }
            else if (d[x3][y3] == '2') {
                flag = true;
                return flag;
            }
            else {
                continue;
            }
        }
    }
    return flag;
}
int main()
{
    //freopen("s.txt", "r", stdin);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char tmpp;
            cin >> tmpp;
            d[i][j] = tmpp;
            a[i][j] = d[i][j];
        }
    }
    for (int i = 0; i < s; i++) {
        int way;
        string strr;
        cin >> way >> strr;
        if (judge(way, strr))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}