网易游戏2016见习生招聘在线笔试 推箱子

这两天又回顾了一下这个题目，整理之后做个保存吧，中间还有点问题，有时间再来改正，自己顺着思路一点点写下来的，逻辑比较简单。

//计算当前的位置
int *findPosition(char **a, int sign, int M, int N){
    int *position = new int[2];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (sign == a[i][j])
            {
                position[0] = i;
                position[1] = j;
            }
        }
    }
    return position;
}
//刷新现在的位置
void refresh(int *person, int *box, int *destination, char **a, int M, int N){
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            a[i][j] = '0';
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (i == person[0] && j == person[1])
            {
                a[i][j] = '1';
            }
            else if (i == box[0] && j == box[1])
            {
                a[i][j] = '3';
            }
            else if (i == destination[0] && j == destination[1])
            {
                a[i][j] = '2';
            }
        }
    }
}

char **moveOneStep(char **a, char move, int M, int N){
    int *person = new int[2];
    int *destination = new int[2];
    int *box = new int[2];
    person = findPosition(a, '1', M, N);
    destination = findPosition(a, '2', M, N);
    box = findPosition(a, '3', M, N);
    if (move == 'r')
    {
        //单独一个人向右移
        if (person[1] + 1 != M&&!(person[1] == box[1] - 1 && person[0] == box[0]))
        {
            person[1] += 1;
            refresh(person, box, destination, a, M, N);
        }//人和箱子一起右移,箱子到达就不能在移动
        else if (person[1] == box[1] - 1 && person[0] == box[0] && box[1] + 1 != M&&!(box[0] == destination[0] && box[1] == destination[1]))
        {
            person[1] += 1;
            box[1] += 1;
            refresh(person, box, destination, a, M, N);
        }
    }
    else if (move == 'd')
    {
        //单独一个人向下移
        if (person[0] + 1 != N&&!(person[0] == box[0] - 1 && person[1] == box[1]))
        {
            person[0] += 1;
            refresh(person, box, destination, a, M, N);
        }//人和箱子一起下移
        else if (person[0] == box[0] - 1 && person[1] == box[1] && box[0] + 1 != N&&!(box[0] == destination[0] && box[1] == destination[1]))
        {
            person[0] += 1;
            box[0] += 1;
            refresh(person, box, destination, a, M, N);
        }
    }
    else if (move == 'l')
    {
        //单独一个人向左移
        if (person[1] - 1 != -1 && !(person[1] == box[1] + 1 && person[1] == box[1]))
        {
            person[1] -= 1;
            refresh(person, box, destination, a, M, N);
        }//人和箱子一起左移
        else if (person[1] == box[1] + 1 && person[1] == box[1] && box[1] - 1 != -1 && !(box[0] == destination[0] && box[1] == destination[1]))
        {
            person[1] -= 1;
            box[1] -= 1;
            refresh(person, box, destination, a, M, N);
        }
    }
    else if (move == 'u')
    {
        //单独一个人向上移
        if (person[0] - 1 != -1 && !(person[0] == box[0] + 1 && person[0] == box[0]))
        {
            person[0] -= 1;
            refresh(person, box, destination, a, M, N);
        }//人和箱子一起上移
        else if (person[0] == box[0] + 1 && person[0] == box[0] && box[0] - 1 != -1 && !(box[0] == destination[0] && box[1] == destination[1]))
        {
            person[0] -= 1;
            box[0] -= 1;
            refresh(person, box, destination, a, M, N);
        }
    }
    return a;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int M, N, S;//N行数，M列数
    cin >> M >> N;
    cin >> S;//测试数
    char **a = new char*[N];
    for (int i = 0; i < N; i++)
        a[i] = new char[M];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> a[i][j];
        }
    }
    //多次循环，做保存用
    char **b = new char*[N];
    for (int i = 0; i < N; i++)
        b[i] = new char[M];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
             b[i][j]=a[i][j];
        }
    }
    //记录初始的目的地位置
    int *destination = new int[2];
    destination = findPosition(a, '2', M, N);
    char c_cin;
    int sum;
    string direction;
    int i = 0;
    while (S--){
        //将a置为原始数据
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                a[i][j] = b[i][j];
            }
        }
        cin >> sum;
        while (sum--)
        {
            cin >> c_cin;
            direction.push_back(c_cin);
        }
        string::iterator dir_iter;
        while (direction.size() != 0)
        {
            dir_iter = direction.begin();
            char move = *dir_iter; 
            direction.erase(dir_iter);
            //开始进行主判断
            a=moveOneStep(a, move, M, N);           
        }
        //判断最后的修改结果
        int *box = new int[2];
        box = findPosition(a, '3', M, N);
        if (destination[0] == box[0] && destination[1] == box[1])
        { 
            cout << "YES" << endl;
        } 
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

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

`