問題 C: 【寬搜入門】8數位難題

【寬搜入門】8數位難題

題目描述

初始狀态的步數就算1，哈哈

輸入：第一個3*3的矩陣是原始狀态，第二個3*3的矩陣是目标狀态。

輸出：移動所用最少的步數

input

2 8 3

1 6 4

7 0 5

1 2 3

8 0 4

7 6 5

output

6

Code

#include<iostream>
#include<queue>
using namespace std;

struct node{
    int x, y;
    int step;
    int M[][];
    int last[];
} Node; 
int X[] = {, , , -};
int Y[] = {, -, , };
int matrix[][], final[][];

bool judge(int x, int y){
    if(x <  || x >=  || y <  || y >= )
        return false;
    return true;
}
bool same(int a[][]){
    for(int i = ; i < ; i++){
        for(int j = ; j < ; j++){
            if(a[i][j] != final[i][j])
                return false;
        }
    }
    return true;
}
int BFS(int x, int y) {
    queue<node> Q;
    Node.x = x, Node.y = y, Node.step = ;
    Node.last[] = x, Node.last[] = y;
    for(int i = ; i < ; i++){
        for(int j = ; j < ; j++){
            Node.M[i][j] = matrix[i][j];
        }       
    }
    Q.push(Node);   
    while(!Q.empty()){
        node top = Q.front();
        Q.pop();

        for(int i = ; i < ; i++){
            int newX = top.x + X[i];
            int newY = top.y + Y[i];        
            if(judge(newX, newY) && (newX != top.last[] || newY != top.last[])){
                Node.x = newX, Node.y = newY;
                Node.step = top.step + ;
                Node.last[] = top.x;
                Node.last[] = top.y;
                for(int i = ; i < ; i++){
                    for(int j = ; j < ; j++){
                        Node.M[i][j] = top.M[i][j];
                    }
                }
                int tmp;
                tmp = Node.M[newX][newY];
                Node.M[top.x][top.y] = tmp;
                Node.M[newX][newY] = ;
                if(same(Node.M)){
                    return Node.step;   
                } 
                Q.push(Node);               
            }   
        }       
    }
    return -;
}
int main(){
    int x, y;
    for(int i = ; i < ; i++){
        for(int j = ; j < ; j++){
            cin >> matrix[i][j];
            if(matrix[i][j] == ){
                x = i;
                y = j;
            }
        }
    }
    for(int i = ; i < ; i++){
        for(int j = ; j < ; j++){
            cin >> final[i][j];
        }
    }
    cout << BFS(x, y) << endl;
}
/**************************************************************
    Problem: 5997
    User: 14041045
    Language: C++
    Result: 正确
    Time:4 ms
    Memory:3240 kb
****************************************************************/
           

嘗試做了每步對矩陣修改的BFS題，還行