回复 7楼 beyondyf
欧拉路径是不是通过节点找最简路径(好像老鼠走迷宫)?这题和欧拉路径还是有区别吧,这题是不是只要输入的单词连成串就行了?
能编个毛线衣吗?
#include <stdio.h> #include <string.h> #define MAX 26 #define SIZE 27 #define LENGTH 1000 int ans[SIZE][SIZE] = { 0 }; int fun() { int i, tmp, res; for (i = 0;i < SIZE;i++) { tmp = abs(ans[i][MAX] - ans[MAX][i]); if (tmp > 1) return 1; res += tmp; } // 链路或环路 return res != 0 && res != 2; } int main() { int T, N; int begin, end, length; char str[LENGTH] = { 0 }; for (scanf("%d", &T);T--;) { memset(ans, 0, sizeof(int) * SIZE * SIZE); for (scanf("%d", &N);N--;) { scanf("%s", str); length = strlen(str); begin = str[0] - 'a'; end = str[length - 1] - 'a'; ans[begin][end] += 1; ans[begin][MAX] += 1; ans[MAX][end] += 1; } printf("%s\n", fun(ans) ? "The door cannot be opened." : "Ordering is possible."); } return 0; }
#include <stdio.h> struct node { int next; char *p; }; int find(node *p,int dp,int l) { int i,j; char a; for(i=0,j=0;i<l;i++) { if(p[i].next >=0)j++; } if(j==l-1) return 1; //如果连成串则返回 for(i=0;p[dp].p[i];i++); a=p[dp].p[i-1]; //找到字符串尾部字符 for(i=0;i<l;i++) { if(i!=dp&&p[i].next <0&&p[i].p[0]==a) { p[dp].next =i; if (find(p,i,l)) return 1; else p[dp].next =-1; } } return 0; } void main() { int i,j; char a[6][10]={"ab","ac","bd","ea","cq","da"}; /*只需定义一个上限为1000的char型数组,然后根据输入再堆里申请实际长度的char数组, 并把指针赋值为结构数组cp相应的指针里,这样可不需要浪费空间*/ node cp[6]; //node数组数量可以是题意里t从堆里申请 for(i=0;i<6;i++) { cp[i].next =-1; cp[i].p=&a[i][0]; printf("%s ",a[i]); } printf("\n"); for(i=0;i<6;i++) { if(find(cp,i,6)) { printf("Ordering is possible.\n"); j=i; while(cp[j].next >=0) { printf("%s-",a[j]); j=cp[j].next ; //显示串链 } printf("\n"); return; } } printf("The door cannot be opened.\n"); }