蓝桥杯历届试题-九宫重排 （C语言代码）

解题思路:bfs&单链表扫描节点和子节点+邻接表查重

注意事项:

下述代码在蓝桥杯官网上全部通过，但是在本网站上有17%的错误，不知道怎么取得那17%的错误测试集。

请大家帮忙看一下我代码的漏洞，谢谢~

参考代码:

#include <stdio.h>

#include <stdlib.h>

typedef struct nob {

int oil[9];

int ceng;

struct nob *next;

struct nob *pnext;

}nob, *stak;

stak star, end;//定义最开始的 

typedef struct pnob {

stak next;

}pnob;

pnob D[9000] = { NULL };//顶点表 

int comp(stak p, stak q) {//比较,相同返回0,否则1 

int i;

for (i = 0; i<9; i++) {

if (p->oil[i] != q->oil[i]) return 1;//

}

return 0;

}

int push(stak p, stak *q, int x, int i) {//入队 

stak n;

stak head;

int tm;

int key = 0, j;

n = (stak)malloc(sizeof(nob));

for (j = 0; j<9; j++) {

n->oil[j] = p->oil[j];//先全部复制，再交换 

}

n->oil[i] = p->oil[i + x];

n->oil[i + x] = p->oil[i];

n->ceng = p->ceng + 1;

//是否等于end

if (comp(n, end) == 0) return 2;//返回 

//要从头开始查找是否有重复

//head = star;

tm = n->oil[0] * 1000 + n->oil[1] * 100 + n->oil[2]*10+ n->oil[3];

if (D[tm].next != NULL) {

head = D[tm].next;

do {

if (comp(head, n) == 0) {

key = 1; break;

}

else head = head->pnext;

} while (head != NULL); //要检查最开始的时候？？

}

if (key != 1) {//没有相同的才加入 

   //p列表 

n->next = (*q)->next;

(*q)->next = n;

*q = (*q)->next;

//头列表 

n->pnext = D[tm].next;

D[tm].next = n;

}

else free(n);//否则没用，free 

return 0;

}

int add(stak p, stak *q) {//把每个节点的子节点加入单链表 

  //p为当前节点，q为表尾 

int i = 0;//找到“.”再第几个

int x, key = 0;

//stak n;//创建 

while (p->oil[i] != 0) i++;

x = i % 3;//横 ,左右 

if (x != 0) key = push(p, q, -1, i);//-1 

if (key == 2) return 2;//找到匹配的 

if (x != 2) key = push(p, q, 1, i);//+1

if (key == 2) return 2;

x = i / 3;//纵 上下 

if (x != 0) key = push(p, q, -3, i);//-3

if (key == 2) return 2;

if (x != 2) key = push(p, q, 3, i);//+3

if (key == 2) return 2;

return 0;

}

void fre(stak star) {//单链表free 

stak p;

while (star->next != NULL) {

p = star;

star = star->next;

free(p);

}

free(star);

}

int main() {

stak p, q;

int num, i;

int tm;

star = (stak)malloc(sizeof(nob));

end = (stak)malloc(sizeof(nob));

q = (stak)malloc(sizeof(nob));

q->ceng = -1;

q->next = NULL;

star->ceng = 0;

end->ceng = 0;

star->next = q;

end->next = NULL;

//for (i = 0; i<900; i++) {

// D[i].next = NULL;

//}

//初始结束值 

for (i = 0; i<9; i++) {

star->oil[i] = getchar() - '0';

if (star->oil[i]<0) star->oil[i] = 0;

}

getchar();

for (i = 0; i<9; i++) {

end->oil[i] = getchar() - '0';

if (end->oil[i]<0) end->oil[i] = 0;

}

p = q = star;//p指向正比较的， q指向表尾 ,head为查重准备 

//comp(&star.oil,&end.oil);

tm = star->oil[0] * 1000 + star->oil[1] * 100 + star->oil[2] * 10 + star->oil[0];

star->pnext = D[tm].next;

D[tm].next = star;

while (p != q->next) {//已经没有其他的可能性了 

if (add(p, &q) == 2)

{

num = p->ceng + 1;

fre(star);

printf("%d", num);

return 0;//因为是再给p.ceng层的add子节点

//所以最后是再p.cneg+1得到

}

p = p->next;

}

fre(star);

num = -1;

printf("%d", num);

return 0;

}