c - 根据元素总和和移动的条件对数组进行排序的程序

Question

You are given a 3x3 array of numbers from 1-9. At each step, you may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.

这是一个问题: http://www.codechef.com/problems/H1

我制作了这个程序，它按照给定的规则对给定的数组进行排序。对于最小翻转次数=7 的数组/拼图，它有效。但对于最少翻转次数超过的数组/拼图，它不起作用。

#include <stdio.h>
#include <stdlib.h>
int a[9]={6,3,5,4,7,2,1,9,8};
//6,3,5,7,9,4,1,8,2
int b[9]={0};
int c[9]={0};
int d[9]={0};
int e[9]={0};
int sortcond=0,count=0;
typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;

Queue * createQueue(int maxElements)
{
        Queue *Q;
        Q = (Queue *)malloc(sizeof(Queue));
        Q->elements = (int *)malloc(sizeof(int)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        return Q;
}
void Dequeue(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                return;
        }
        else
        {
            Q->size--;
                Q->front++;
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}
int front(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                exit(0);
        }
        return Q->elements[Q->front];
}


void Enqueue(Queue *Q,int element)
{
        if(Q->size == Q->capacity)
        {
               printf("Queue is Full\n");
        }
        else
        {
                Q->size++;
                Q->rear = Q->rear + 1;
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                    Q->elements[Q->rear] = element;
        }
        return;
}

void enqueue(Queue *Q,int *element)
{
    int i;
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full\n");
        }
        else
        {
            for(i=0;i<9;i++){
                Q->size++;
                Q->rear = Q->rear + 1;
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                    Q->elements[Q->rear] = *(element+i);

                    }
        }
        return;
}

void EnQueue(Queue *Q,int *element)
{

    int i;
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full\n");
        }
        else
        {
             Q->elements[Q->rear] = *element;

            for(i=1;i<9;i++){
                Q->size++;
                Q->rear = Q->rear + 1;
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                    Q->elements[Q->rear] = *(element+i);

                    }
        }
        return;
}

Queue *que,*seen;

int primecheck(int num1,int num2){
    switch(num1+num2){
        case  3:
        case  5:
        case  7:
        case 11:
        case 13:
        case 17:
        return 1;
    }
    return 0;
}

int possibleflips(){
int validpair[12][2] = { {0,1}, {1,2}, {3,4}, {4,5}, {6,7}, {7,8}, {0,3}, {3,6}, {1,4}, {4,7}, {2,5}, {5,8} };
int i,j,p,q,temp,seencond,seencond2;
//printf("entered possibleflips\n");
for(i=0;i<12;i++){
    int p = validpair[i][0];
    int q = validpair[i][1];
    if(primecheck(b[p],b[q])){
        for(j=0;j<9;j++){
            c[j]=b[j];
        }
        temp=c[p];
        c[p]=c[q];
        c[q]=temp;
        while(front(seen)!=0){
        seencond=1;
        seencond2=0;
        for(j=0;j<9;j++){
            d[j]=front(seen);
           if(c[j]==front(seen));
           else
            seencond=0;
           Dequeue(seen);
        }
        enqueue(seen,d);
        if(seencond==1){
            seencond2=1;
        }
        }
        if(seencond2==0){
            EnQueue(seen,c);
            Enqueue(seen,0);
            enqueue(que,c);
        }
        else{
            Dequeue(seen);
            Enqueue(seen,0);
        }
    }
}
//printf("exit possibleflips\n");
return;
}

int searching(){
    int  i,cond;
    //printf("entered search\n");
while(front(que)!=0){
        cond=1;
    for(i=0;i<9;i++){
            e[i]=front(que);
        if(front(que)==i+1);
        else
            cond=0;
        Dequeue(que);
    }
    enqueue(que,e);
    if(cond==1){
        sortcond=1;
        return;
    }
}
Dequeue(que);
Enqueue(que,0);
//printf("exit search\n");
return;
}

int firststep(){
int i;
//printf("firststep\n");
while(sortcond==0){
    while(front(que)!=0){
            for(i=0;i<9;i++){
                b[i]=front(que);
                //printf("%d ",b[i]);
                Dequeue(que);
            }
            //printf("\n");
    possibleflips();
}
Dequeue(que);
Enqueue(que,0);
searching();
count++;
}
return;
}

int main()
{
    int i;
    que=createQueue(5000000);
    seen=createQueue(5000000);
    enqueue(que,a);
    Enqueue(que,0);
    enqueue(seen,a);
    Enqueue(seen,0);
    firststep();
    printf("count %d", count);
    return 0;
}

a[] 是给定的数组(您可以输入一些简单的问题，例如 1,3,2,4,5,6,7,8,9)，它适用于它们。

它首先将给定的数组添加到队列中，然后找到可以在给定数组上进行一次交换的数组，然后将它们添加到队列中，然后从队列中删除给定的数组。搜索其中任何一个是否为 1,2..9。如果没有，那么它会找到可以在一次交换中进行的数组，即与给定数组的两次交换，并将它们添加到队列中，依此类推。它还检查案例的重复情况。

适用于最小翻转次数低于 7 的数组，例如{6,3,5,7,9,4,1,8,2}。但对于最少翻转次数大于此数的数组，例如{6,3,5,4,7,2,1,9,8}，它不起作用。

Answer 1

我无法浏览您提供的整个代码，但据我所知，您不会检查部分结果的唯一性:您永远不知道棋盘状态是否已被检查。因此，您的代码会进行相同的来回翻转，多次重复相同的分析。相同的板状态一次又一次排队，导致数据结构溢出。

添加另一个队列，例如。 Queue *seen; ，以测试所有数字的排列，并检查 posflips() 中的每个新排列。如果它已经在 seen 中。如果是这样，请忽略排列，否则将其都添加到 qu并发送至seen .

附注。
你知道数字只有 1 到 9，所以两个数之和可以是 3 到 17，因此只有 6 个可能的素数，而你的 primecheck()可以简化为

int primecheck(int numloc1,int numloc2){
    switch(numloc1+numloc2){
        case  3:
        case  5:
        case  7:
        case 11:
        case 13:
        case 17:
            return 1;
    }
    return 0;
}

你的棋盘上共有 36 对牌，其中只有 12 对是相邻的牌。所以 primecheck() 的 2/3 posflips() 中完成的调用都是无用的。您应该调用check()首先且仅当成功调用 primecheck() 时，像这样:

if(check(i,j) && primecheck(c[i],c[j])){
    //....
}

此外，您可以删除 check()根本不。您的棋盘非常小，因此枚举所有有效的仓位对可能比测试每对仓位的有效性更容易:

int validPair[12][2] = {
    {0,1}, {1,2}, {3,4}, {4,5}, {6,7}, {7,8},
    {0,3}, {3,6}, {1,4}, {4,7}, {2,5}, {5,8}
};
int p;
for(p=0;p<12;p++){
    int i = validPair[p][0];
    int j = validPair[p][1];
    if(primecheck(c[i],c[j])){
        // ... do flips
        // ... check flipped board against 'seen' queue
        // ... and Enqueue if the board not seen before
    }

编辑

如果您重命名seencond至arraysAreEqual和seencond2至arrayWasSeen初始化将会变得非常明显

arrayWasSeen=0;

以前

seencond2=0;

应该位于 while 之前循环。

注意:当您在单独的位置构造翻转数组时，您不需要 temp变量 – 只需交叉复制原始数组中的两项:

for(j=0;j<9;j++)
    c[j]=b[j];
c[p]=b[q];
c[q]=b[p];