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

Question

给出您从1到9的3x3数字数组。 在每一步，如果它们的总和是一个质数，你可以交换两个相邻的瓷砖。如果两个瓷砖有共同的边缘，则认为它们相邻。

这是从一个问题： 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; 
} 

一个[]是给定的数组（你可以把一些简单的问题，像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。

PS。
你知道的数字是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()在posflips()中的2/3的调用是无用的。你应该叫check()第一且仅当它succeedes调用primecheck()，像这样：

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

在addidtion，你可以摆脱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];