HDU 1254プッシュボックス

大まかな考え方:(双bfs)1:まず2,3,4の位置を記録する2:箱に対してbfsを行い箱を押す4方向を設け、3次元配列で人と箱の状態を記録する【箱横座標】【箱縦座標】【押す方向】(状態を繰り返さない)3:人に対してbfsを進める2と同時に、人が箱が押されたときに人がいるべき位置に達できるかどうかを判断します.以下は私がojに合格していないコードで、先に上を貼ってから間違いの原因を研究します.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n, m;
int vis[80][80];
int direction[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
struct node{
    int x, y;
    int steps;
    int map[10][10];
};
node box_start, box_end, person_end, person_start;
node moved_box;
node init;
node moved_person;
node person;
bool judge(node s){
    if (s.x >= 0 && s.y >= 0 && s.x < n&&s.y < m&&vis[s.x][s.y] != 1)
        return true;
    return false;
}
bool person_bfs(node nnn){          //         ，                         ，             
    node maps = nnn;                //  
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (maps.map[i][j] == 4){
                person.x = i, person.y = j;
            }
        }
    }
    if (maps.map[person_end.x][person_end.y] == 4)return true;      //                ，    
    int flag[10][10];
    memset(flag, 0, sizeof(flag));
    queue q;
    maps.x = person_end.x, maps.y = person_end.y;

    flag[maps.x][maps.y] = 1;
    q.push(maps);
    while (!q.empty()){
        node temp = q.front(); q.pop();
        for (int i = 0; i < 4; i++){

            moved_person.x = temp.x + direction[i][0];
            moved_person.y = temp.y + direction[i][1];
            if (judge(moved_person) && !flag[moved_person.x][moved_person.y] && maps.map[moved_person.x][moved_person.y] != 2){
                flag[moved_person.x][moved_person.y] = 1;
                if (maps.map[moved_person.x][moved_person.y] == 4)
                    return true;
                q.push(moved_person);
            }
        }
    }
    return false;
}
int box_bfs(){
    int flag[20][20][20];
    memset(flag, 0, sizeof(flag));
    queue q;
    q.push(box_start);
    while (!q.empty()){
        node box_start_temp = q.front(); q.pop();   //       
        for (int i = 0; i < 4; i++){
            moved_box = box_start_temp;
            moved_box.x = box_start_temp.x + direction[i][0];   //        
            moved_box.y = box_start_temp.y + direction[i][1];
            person_end.x = box_start_temp.x - direction[i][0];  //             
            person_end.y = box_start_temp.y - direction[i][1];
            if (judge(moved_box) && judge(person_end) && !flag[moved_box.x][moved_box.y][i]){       //    
                if (person_bfs(moved_box)){     //           ，      
                    swap(moved_box.map[moved_box.x][moved_box.y], moved_box.map[box_start_temp.x][box_start_temp.y]);
                    swap(moved_box.map[box_start_temp.x][box_start_temp.y], moved_box.map[person.x][person.y]);
                    moved_box.steps++;
                    flag[moved_box.x][moved_box.y][i] = 1;
                    if (moved_box.x == box_end.x&&moved_box.y == box_end.y)
                        return moved_box.steps;
                    q.push(moved_box);
                }

            }
        }
    }
    return -1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--){
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            scanf("%d", &vis[i][j]);
            init.map[i][j] = vis[i][j];
        }
        init.steps = 0;
        box_start = init;
        for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            if (vis[i][j] == 2)box_start.x = i, box_start.y = j;
            if (vis[i][j] == 3)box_end.x = i, box_end.y = j;
        }
        cout << box_bfs() << endl;
    }
    return 0;
}