一. 程序设计想法：
于是这次我实在是懵了...真的不会啊...(好在后来得知是个np问题)...
于是听从老师的建议，先从判定算法写起...
于是第一反应这是一个八方搜索啊
我从1~n,1~n表示一个二维字符矩阵，不从0开始的好处是防止溢出。
dfs(int x,int y,int direct,int num,int k)
分别表示此时搜到的坐标为(x,y)，方向为direct(若为0则启动1~8循环方向)，num为此时序列符合第几个单词(若为-1则启动1~count循环判定符合与否)，k表示此时为第num个单词的第k个字母(当k==第num个单词长度时，则搜到完整单词)。
似乎就是一个全排列类似的写法。
需要记录的就是给定的count个单词是否被覆盖且仅被覆盖一次，二维字符矩阵中的每个字符被覆盖了多少次，是否4个顶点都被覆盖，是否有一行或一列没有被覆盖，是否8个方向都满足数量。
似乎简单但写起来却挺费劲。前几天刚写了个数独的解法，用的就是类似的搜索...事实证明可行...
但是
同组小伙伴王文涛提出：我为什么不能暴力一下? 就是对每一个字符进行和给定字符串第一个字符匹配，如果相同则八方暴力搜索。
真暴力！但似乎和搜索的时间复杂度差不多0.0
于是就给他搞了...
我来写生成算法T.T怎么能这样！
还是老办法，分步写...
第一个模块：字符串预处理，把中间空格去掉
1 int StringPretreatment(int Temp) 2 { 3 int Length = strlen(StringInput[Temp]); 4 for (int i = 0;i < Length;i++) 5 { 6 if (StringInput[Temp][i] == ' ') 7 { 8 for (int j = i + 1;j < Length;j++) 9 StringInput[Temp][j - 1] = StringInput[Temp][j];10 StringInput[Temp][Length - 1] = EOF;11 Length--;i--;12 }13 }14 return Length;15 } 第二个模块：字符串按长度排序(由于数量不多我就用冒泡了)
1 void StringSort() 2 { 3 int i,j,k; 4 char StringTemp[25]; 5 for (i = 0;i < StringCount - 1;i++) 6 for (j = i + 1;j < StringCount;j++) 7 if (StringLength[i] < StringLength[j]) 8 { 9 k = StringLength[i];10 StringLength[i] = StringLength[j];11 StringLength[j] = k;12 strcpy(StringTemp,StringInput[i]);13 strcpy(StringInput[i],StringInput[j]);14 strcpy(StringInput[j],StringTemp);15 }16 } 我的想法是用2个横&2个竖填充四条边，保证每个单词占据一个顶点，构成一个“卍”(没有中间的十字)
于是代码如下：
1 void FirstStep() 2 { 3 int i,j; 4 for (i = 0;i < maxN;i++) 5 for (j = 0;j < maxN;j++) OutputMatrix[i][j] = ' '; 6 for (i = 0;i < StringLength[0];i++) 7 OutputMatrix[0][i] = StringInput[0][i]; 8 for (i = 0;i < StringLength[1];i++) 9 OutputMatrix[maxN - 1][maxN - StringLength[1] + i] = StringInput[1][i];10 for (i = 0;i < StringLength[2];i++)11 OutputMatrix[maxN - StringLength[2] + i][0] = StringInput[2][i];12 for (i = 0;i < StringLength[3];i++)13 OutputMatrix[i][maxN - 1] = StringInput[3][i];14 } 接着继续生成字符矩阵，由于横向正&竖向正已经满足条件，于是我偷懒的不写这两种情况了，剩下的字符串都以剩下6种填充。
我的办法是暴力填充，所选位置为此字符串满足填充条件的第一个位置，因此也就没法保证最小性，但是要是使用dfs枚举所有位置，时间肯定会爆掉。
选取每个字符串走向的办法是对字符串序号取模，对应剩下6种走向。
1 int StringJudge(int direct,int num,int x,int y) 2 { 3 int i,flag = 0,res = 0; 4 if (direct == 0) 5 { 6 if (y >= StringLength[num]) 7 { 8 for (i = 0;i < StringLength[num];i++) 9 if (OutputMatrix[x][y - i] != ' ' 10 && OutputMatrix[x][y - i] != StringInput[num][i]) flag = 1; 11 if (flag == 0) res = 1; 12 } 13 } 14 if (direct == 1) 15 { 16 if (x >= StringLength[num]) 17 { 18 for (i = 0;i < StringLength[num];i++) 19 if (OutputMatrix[x - i][y] != ' ' 20 && OutputMatrix[x - i][y] != StringInput[num][i]) flag = 1; 21 if (flag == 0) res = 1; 22 } 23 } 24 if (direct == 2) 25 { 26 if ((StringLength[num] + x) <= maxN && (StringLength[num] + y) <= maxN) 27 { 28 for (i = 0;i < StringLength[num];i++) 29 if (OutputMatrix[x + i][y + i] != ' ' 30 && OutputMatrix[x + i][y + i] != StringInput[num][i]) flag = 1; 31 if (flag == 0) res = 1; 32 } 33 } 34 if (direct == 3) 35 { 36 if (x >= StringLength[num] && y >= StringLength[num]) 37 { 38 for (i = 0;i < StringLength[num];i++) 39 if (OutputMatrix[x - i][y - i] != ' ' 40 && OutputMatrix[x - i][y - i] != StringInput[num][i]) flag = 1; 41 if (flag == 0) res = 1; 42 } 43 } 44 if (direct == 4) 45 { 46 if (y >= StringLength[num] && (x + StringLength[num]) <= maxN) 47 { 48 for (i = 0;i < StringLength[num];i++) 49 if (OutputMatrix[x + i][y - i] != ' ' 50 && OutputMatrix[x + i][y - i] != StringInput[num][i]) flag = 1; 51 if (flag == 0) res = 1; 52 } 53 } 54 if (direct == 5) 55 { 56 if (x >= StringLength[num] && (y + StringLength[num]) <= maxN) 57 { 58 for (i = 0;i < StringLength[num];i++) 59 if (OutputMatrix[x - i][y + i] != ' ' 60 && OutputMatrix[x - i][y + i] != StringInput[num][i]) flag = 1; 61 if (flag == 0) res = 1; 62 } 63 } 64 return res; 65 } 66 void StringIntoMatrix(int direct,int num,int x,int y) 67 { 68 int i; 69 if (direct == 0) 70 { 71 for (i = 0;i < StringLength[num];i++) OutputMatrix[x][y - i] = StringInput[num][i]; 72 } 73 if (direct == 1) 74 { 75 for (i = 0;i < StringLength[num];i++) OutputMatrix[x - i][y] = StringInput[num][i]; 76 } 77 if (direct == 2) 78 { 79 for (i = 0;i < StringLength[num];i++) OutputMatrix[x + i][y + i] = StringInput[num][i]; 80 } 81 if (direct == 3) 82 { 83 for (i = 0;i < StringLength[num];i++) OutputMatrix[x - i][y - i] = StringInput[num][i]; 84 } 85 if (direct == 4) 86 { 87 for (i = 0;i < StringLength[num];i++) OutputMatrix[x + i][y - i] = StringInput[num][i]; 88 } 89 if (direct == 5) 90 { 91 for (i = 0;i < StringLength[num];i++) OutputMatrix[x - i][y + i] = StringInput[num][i]; 92 } 93 } 94 void MatrixProduce(int StringNum) 95 { 96 int StringDirect = StringNum % 6; 97 int i,j,flag = 0,suit; 98 for (i = 0;i < maxN;i++) 99 {100 for (j = 0;j < maxN;j++)101 {102 if (OutputMatrix[i][j] == ' ' || OutputMatrix[i][j] == StringInput[StringNum][0])103 {104 suit = StringJudge(StringDirect,StringNum,i,j);105 if (suit == 1)106 {107 StringIntoMatrix(StringDirect,StringNum,i,j);108 flag = 1;109 }110 }111 if (flag == 1) break;112 }113 if (flag == 1) break;114 }115 } 这样似乎就可以了...当然只要maxN足够大的话，肯定能够把所有字符串放进去，满足全部条件除没有一行一列都是无用字符。
对于那组比较少的数据：
于是空格就是随意填的字符...
需要注意的是，我设定的第一步要求最小的maxN要比最长单词长度大1。
对于那组比较多的数据：
我们能做到20*20的矩阵，这是我们程序能找到的最小解。
最下面两个数字代表总共多少个单词以及成功打印了多少个单词。
二. 时间安排：
| 预计时间 | 5h | 实际用时 | 6h |
| 代码规范 | 0.5h | 0.5h | |
| 具体设计 | 0.5h | 1h | |
| 具体编码 | 2.5h | 3h | |
| 代码复审 | 0.5h | 0h | |
| 代码测试 | 0.5h | 1h | |
| 测试报告 | 0.5h | 0.5h |
三. 官方样例测试：(测试程序为王文涛所写)
test1
test2
test3
test4我们试了很多种生成算法(改变不同走向)，结果还是通不过检测。
后来............
MUM是无论如何也通不过测试的啊！！！
忽略...
test5
就是这样了...算是较优解吧...
检测代码请见王文涛blogs。