codechef：益智游戏

Question

问题陈述：

约翰尼在记忆小质数方面有些困难。所以，他的计算机老师经常让他玩下面的益智游戏。

拼图是一个 3x3 的棋盘，由 1 到 9 的数字组成。拼图的 objective 是交换方块，直到达到以下最终状态：

1 2 3
4 5 6
7 8 9

在每一步中，约翰尼可以交换两个相邻的牌，如果它们的总和是素数。如果两个图块有公共边，则认为它们相邻。

帮助约翰尼找出达到目标状态所需的最短步数。

我目前的解决方案

#include<bits/stdc++.h>

using namespace std;

bool prime[20];

int matrix[3][3];
int solved[3][3] = {
    {1,2,3},
    {4,5,6},
    {7,8,9}
};

void display()
{
    for(int row = 0; row<3;row++)
        {
            for(int col = 0;col<3;col++)
            {
                cout<<matrix[row][col]<<" ";
            }
            cout<<endl;
        }
        cout<<endl<<endl;

}

bool check(){
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(matrix[i][j]!=solved[i][j])
                return false;
        }
    }
    return true;
}

int min(int a,int b)
{
    return (a<b)?a:b;
}

void generate(){
    memset(prime,true,sizeof(prime));
    for(int i=2;i*i<20;i++){
        if(prime[i]==true)
        {
            for(int j=2*i;j<20;j+=i)
                prime[j]=false;
        }
    }
}

int getMoves(int row, int col){
    if(row < 0 ||col< 0 || row>=3||col>=3){
        return 0;
    }
    if(check()){
        return 0;
    }

    int moves = 0;

    for(int i = row-1 ; i<= row+1 ;i++)
    {
        for(int j = col -1 ; j<=col+1;j++)
        {
            if((i!=row-1&&j!=col-1)||(i!=row+1&&j!=col+1)||(i!=row+1&&j!=col-1)||(i!=row-1&&j!=col+1)){

                if(prime[matrix[row][col]+matrix[i][j]]==true)
                {
                    moves+=getMoves(i,j);
                    int temp;
                    temp = matrix[i][j];
                    matrix[i][j] = matrix[row][col];
                    matrix[row][col] = temp;
                    display();
                }
            }   
        }
    }
    return moves;
}

int Moves(){
    int minMoves = INF;
    for(int row = 0;row<3;row++)
    {
        for(int col = 0;col<3;col++)
        {
            int moves = getMoves(row,col);
            minMoves = min(moves,minMoves);
        }
    }
    return minMoves;
}



int main(){
    generate();
    int t;
    cin>>t;
    while(t--)
    {
        for(int row = 0; row<3;row++)
        {
            for(int col = 0;col<3;col++)
            {
                cin>>matrix[row][col];
            }
        }

    }
    cout<<Moves();
}

示例测试用例

Input:
2

7 3 2 
4 1 5 
6 8 9 

9 8 5 
2 4 1 
3 7 6  

Output:
6
-1

程序一直崩溃我猜是因为内存溢出问题。

Answer 1

if (row < 0 || col< 0 || row >= 3 || row <= 3) {
    return 0;
}

这部分之后的代码是'not accessible'，因为这个条件总是为真(... row >= 3 || row <= 3)。您可能打算写：(... row >= 3 || col >= 3)

Answer 2

恐怕你的代码是完全错误的，我认为如果不完全重写它就无法修复。例如，在函数 getMoves() 中，您的变量 i 和 j 可以获得值 -1，因此您将面临访问冲突错误。其次，你在那里有一个递归，但你在调用递归之前不更改数据。假设你想交换 7 和 4。在下一步中（因为你没有改变输入）你可以交换 4 和 1。但这不是正确的举动，因为在那个时候，4 不应该在那里。第三，你的函数 getMoves() 可以无限循环结束。

总之，这类问题的解决方式大不相同。例如，您可以使用 backtracking algorithm or you can use A* algorithm。你将不得不评估你目前的状态。假设以下状态：

7 3 2
4 5 6
1 8 9

您可以测量数字到达正确位置所需的移动次数。所以在这种情况下 1 必须做 2 步，7 必须做 2 步，2 必须做 1 步以及数字 3。该状态的值为2 + 2 + 1 + 1 = 6。它被称为启发式函数。现在您可以将此函数放入 A* 算法中，您应该会看到正确的结果。

codechef：益智游戏

codechef: A puzzle game

c++

algorithm

depth-first-search