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

古城微笑少年丶 2022-08-04 15:33 329阅读 0赞

### 题目描述 ###

![bsFpCsp.png][]  
![Ox5aid7.png][]

### 解题思路 ###

对于输入的状态，找出玩家和箱子的位置，并使用坐标记录其位置，然后对于终端输入的走法，依次判断player按该走法一步一步的移动之后是否能够成功。由于思路比较简单，实际内容就是如何让计算机模拟这个推箱子的过程。步骤也很简单，只有上下左右移动，但是需要注意的是每次移动之前，需要对于题目描述的集中状态和情况进行判断，保证每一种情形都考虑到而且不重复判断。另外还需要注意的一点是，**每次移动完成之后，需要对棋盘以及玩家和箱子的位置和状态进行更新**，以便于真正模拟了游戏的过程。

### 实现代码 ###

#include<iostream>
        #include<string>
    
        using namespace std;
    
        char chessboard[100][100]; // 棋盘布局
        char chessboard_bkup[100][100]; // 棋盘布局
        char path[200][10000]; // 推动路径
        int path_count[10000];
        string results[10000]; // 记录每一个玩法的最终胜负状态
    
        int main(){
            int N =0,M = 0,S = 0;
            cin>>N>>M>>S;
            int player_m = 0,player_n = 0; // 玩家的坐标
            int player_m_bkup = 0,player_n_bkup = 0;
            int box_m = 0,box_n = 0; // 箱子的坐标
            int box_m_bkup = 0,box_n_bkup = 0;
    
            bool flag_1 = true,flag_2 = true;
            for(int m=0;m<M;m++){ // M行
                cin>>chessboard_bkup[m];
                for(int n=0;n<strlen(chessboard_bkup[m]);n++){
                    if(flag_1 == true){
                        if(chessboard_bkup[m][n] == '1'){ // 玩家的位置
                            player_m_bkup = m;
                            player_n_bkup = n;
                            flag_1 = false;
                        }
                    }
                    if(flag_2 == true){
                        if(chessboard_bkup[m][n] == '3'){ // 箱子的位置
                            box_m_bkup = m;
                            box_n_bkup = n;
                            flag_2 = false;
                        }
                    }
                }
            }
    
            for(int i=0;i<S;i++) // 读取走法需要的步数和具体走法
                cin>>path_count[i]>>path[i];
    
            bool flag = false;
            for(int i=0;i<S;i++){
                // 每一次移动之后都需要判断是否已经到了目标位置
                // 在箱子的每次移动的时候需要判断将要移动的位置是否是目标位置，如果不是，需要对棋盘布局进行修改
                // 修改的棋盘是输入棋盘的一个副本
                flag = false;
                player_m = player_m_bkup;
                player_n = player_n_bkup;
                box_m = box_m_bkup;
                box_n = box_n_bkup;
                for(int p=0;p<M;p++)
                    for(int q=0;q<N;q++)
                        chessboard[p][q] = chessboard_bkup[p][q];
    
                for(int j=0;j<path_count[i];j++){
                    if(path[i][j] == 'u'){ // 上移
                        if(chessboard[player_m-1][player_n] == '3'){ // 移动方向上有箱子
                            if(chessboard[player_m-2][player_n] == '0' || chessboard[player_m-2][player_n] == '2'){ // 移动方向没有被墙壁挡住
                                if(chessboard[player_m-2][player_n] == '2'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m-1][player_n] = '1';
                                    player_m-=1;
                                    box_m-=1; 
                                    flag = true;
                                    results[i] = "YES";
                                }else{
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m-1][player_n] = '1';
                                    chessboard[player_m-2][player_n] = '3';
                                    player_m-=1;
                                    box_m-=1; 
                                }
                            } // 若被挡住则什么也不做
                        }else{
                            if(chessboard[player_m-1][player_n] == '0' || chessboard[player_m-1][player_n] == '2'){
                                if(chessboard[player_m-1][player_n] == '0'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m-1][player_n] = '1';
                                    player_m-=1; // 如果移动方向没有箱子，且没有墙壁阻挡，只移动玩家
                                }else{
                                    player_m-=1;
                                }
                            }
                        }
                    }
                    if(path[i][j] == 'd'){ // 下移
                        if(chessboard[player_m+1][player_n] == '3' || chessboard[player_m+2][player_n] == '2'){ 
                            if(chessboard[player_m+2][player_n] == '2'){
                                chessboard[player_m][player_n] = '0';
                                chessboard[player_m+1][player_n] = '1';
                                player_m+=1;
                                box_m+=1; 
                                flag = true;
                                results[i] = "YES";
                            }else{
                                chessboard[player_m][player_n] = '0';
                                chessboard[player_m+1][player_n] = '1';
                                chessboard[player_m+2][player_n] = '3';
                                player_m+=1;
                                box_m+=1;  
                            } 
                        }else{
                            if(chessboard[player_m+1][player_n] == '0' || chessboard[player_m+1][player_n] == '2'){
                                if(chessboard[player_m][player_n+1] == '0'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m+1][player_n] = '1';
                                    player_m+=1;
                                }else{
                                    player_m+=1;
                                }
                            }
                        }
                    }
                    if(path[i][j] == 'l'){ // 左移
                        if(chessboard[player_m][player_n-1] == '3'){ 
                            if(chessboard[player_m][player_n-2] == '0' || chessboard[player_m][player_n-2] == '2'){ 
                                if(chessboard[player_m][player_n-2] == '2'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m][player_n-1] = '1';
                                    player_n-=1;
                                    box_n-=1; 
                                    flag = true;
                                    results[i] = "YES";
                                }else{
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m][player_n-1] = '1';
                                    chessboard[player_m][player_n-2] = '3';
                                    player_n-=1;
                                    box_n-=1;  
                                } 
                            }
                        }else{
                            if(chessboard[player_m][player_n-1] == '0' || chessboard[player_m][player_n-1] == '2'){
                                if(chessboard[player_m][player_n+1] == '0'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m][player_n-1] = '1';
                                    player_n-=1;
                                }else{
                                    player_n-=1;
                                }
                            }
                        }
                    }
    
                    if(path[i][j] == 'r'){ // 右移
                        if(chessboard[player_m][player_n+1] == '3'){ 
                            if(chessboard[player_m][player_n+2] == '0' || chessboard[player_m][player_n+2] == '2'){ 
                                if(chessboard[player_m][player_n+2] == '2'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m][player_n+1] = '1';
                                    player_n+=1;
                                    box_n+=1; 
                                    flag = true;
                                    results[i] = "YES";
                                }else{
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m][player_n+1] = '1';
                                    chessboard[player_m][player_n+2] = '3';
                                    player_n+=1;
                                    box_n+=1;  
                                } 
                            }
                        }else{
                            if(chessboard[player_m][player_n+1] == '0' || chessboard[player_m][player_n+1] == '2'){
                                if( chessboard[player_m][player_n+1] == '0'){
                                    chessboard[player_m][player_n] = '0';
                                    chessboard[player_m][player_n+1] = '1';
                                    player_n+=1;
                                }else{
                                    player_n+=1;
                                }
                            }
                        }
                    }
                }
    
                if(flag == false)
                    results[i] = "NO";
            }       
    
            for(int i=0;i<S;i++){
                cout<<results[i]<<endl;
            }
    
            return 0;
        }

### 测试输出 ###

测试用例和测试结果如下：

![YdOL5Ck.png][]  
![JGzyqLK.png][]

箱子在目标点上输出为YES，否则输出为NO

代码中对于状态和棋盘都是使用的备份内容中实现的，由于时间紧迫，当时采用了这种临时的做法，后来看看，没有太多的必要使用一份备份来进行操作。不过对于推箱子的过程以及状态判断和棋盘更新部分的代码思路还是正确的。

[bsFpCsp.png]: http://i.imgur.com/bsFpCsp.png
[Ox5aid7.png]: http://i.imgur.com/Ox5aid7.png
[YdOL5Ck.png]: /images/20220731/6ac7a175d6eb40c5b5e27f479d8a8f41.png
[JGzyqLK.png]: http://i.imgur.com/JGzyqLK.png