Question

求C语言编程大佬帮忙！这道题的逻辑哪里出错了！找了几个小时了没搞明白！

方格填数如下的10个格子填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。#include <stdio.h>#include <iostream>using namespace std;int number=0;bool b[10];int a[3][4];void pd(){ bool HH=1; for(int i=0;i<3;i++) { for(int j=0;j<3;i++) if( !( (a[i][j]-a[i][j+1]!=1) && (a[i][j]-a[i][j+1]!=-1) ) )HH=0; } for(int i=0;i<3;i++) //判断是否上下，上下斜方向临近 { for(int j=i-1;j<=i+1;j++) { if( !( (j<=3) &&(j>=0) && ((a[1][i]-a[0][j])!=1) && ((a[1][i]-a[0][j])!=-1) ))HH=0; if( !( (j<=3) &&(j>=0) && ((a[1][i]-a[2][j])!=1) && ((a[1][i]-a[2][j])!=-1) ))HH=0; } } if(HH)number++; printf("number");}void fuzhi(int c[],int enter){ if(enter==10) { for(int i=0;i<=2;i++) //将C【12】的值给A【3】【4】； { for(int j=0;j<=3;j++) { if(i+j==0||i*4+j==11)a[i][j]=999; else a[i][j]=c[i*4+j]; } } pd(); return; } for(int i=0;i<=9;i++) { if(!( b[i])){ c[enter]=i; b[i]=1; fuzhi(c,enter+1); } b[i]=0; } }int main(){ int c[10]; fuzhi(c,0); cout<<number<<endl<<"123"<<endl;// printf("1!" );// printf("%d!",number); return 0;}

Answer 1

代码有点乱，不太看得清思路，里面有一些数组越界访问的情况，算法是否有效未知，重写了一个供参考。

思路如下：

这个问题实际上是生成0~9的全排列，然后根据每个数在格子里的位置判断每个排列是否符合要求。百度了一个全排列算法稍做修改，得到以下代码，输出的有效方案数是1580，在我这里输出大约在70ms到100ms左右。百度这个代码排版垃圾得无以复加，vs里面排得好好复制过来全乱，不再重排了。

另外，生成排列数以后，这个格子问题其实应该能转化为纯数学算法来判断，不需要真的填什么表的，我懒得想太多，填表和判断部分的代码有点玩的性质。

#include <stdio.h>
//#include <time.h>  // 测试执行时间的 GetTickCount() 引用 
//#include <Windows.h> // 测试执行时间的 GetTickCount() 引用
const int ROW = 5;  // 增加两行用于减少边界判断，实际使用中间3行
const int COL = 6;  // 增加两列用于减少边界判断，实际使用中间4列
const int BORDER = -11; // 表格边界标记
const int NON = -9;  // 标记表格有效内容的起止位置

int grid[ROW][COL]; // 表格数组
int count;   // 有效方案计数
void InitGrid(void);     // 初始化表格，设置边界和标记表格有效内容的起止位置
void PrintGrid(void);     // 打印输出有效方案    
void Perm(int list[], int k, int m); // 递归生成排列数，生成的排列数输出到表格中，然后判断是否打印和计数
void Swap(int &a, int &b);    // 引用、交换函数，用于递归生成排列数函数
void PermOutput(int list[]);   // 排列数填表、判断、打印、计数

void main(void)
{
//long start_time, end_time;   // 记录测试执行时间起止的变量
int num[10] = { 0,1,2,3,4,5,6,7,8,9 }; // 0~9 数值序列
//start_time = GetTickCount();   // 获取此程序段开始执行时间
    
count = 0;
InitGrid();
Perm(num, 0, 10);
//end_time = GetTickCount();   //获取此程序段执行结束时间
//printf("\nCount = %d in %ld ms\n", count, end_time - start_time); // 打印输出程序执行时间
getchar();
}

// 初始化表格，设置边界和标记表格有效内容的起止位置
void InitGrid(void)
{
int i, j;
    
for (i = 0; i < ROW; i++)
{
for (j = 0; j < COL; j++)
{
grid[i][j] = BORDER; // 设置边界
}
}
// 设置有效内容的起止位置
grid[1][1] = NON;
grid[ROW - 2][COL - 2] = NON;
}

// 打印输出有效方案
void PrintGrid(void)
{
int i, j;
    
printf("  - - - - - - - - - - -\n");
for (i = 1; i < ROW - 1; i++)
{
for (j = 1; j < COL - 1; j++)
{
if (grid[i][j] != NON)
printf("%5d", grid[i][j]); // 有效值
else
printf("%5s", "");   // 有效值起止位置
}
printf("\n");
}
}

// 递归生成排列数，生成的排列数输出到表格中，然后判断是否打印和计数
void Perm(int list[], int k, int m) // k表示前缀的位置，m是要排列的数目。
{
int i;
if (k == m - 1) // 前缀是最后一个位置，表示m位排列数已生成，判断是否有效方案并打印和记数。
{
PermOutput(list);
}
else   // 否则进入递归生成一下个排列数位
{
for (i = k; i<m; i++)
{
//交换前缀,使之产生下一个前缀.
Swap(list[k], list[i]);
Perm(list, k + 1, m);
//将前缀换回来,继续做上一个的前缀排列.
Swap(list[k], list[i]);
}
}
}

// 引用、交换函数，用于递归生成排列数函数
void Swap(int &a, int &b)
{
int temp = a; a = b; b = temp;
}
// 排列数填表、判断、打印、计数
void PermOutput(int list[])
{
int i, j, n; // n用于引用grid[i][j]的值提高效率
bool ok;  // 方案有效标记
// 将排列数填入表格中
n = 0;
for (i = 1; i < ROW - 1; i++)
{
for (j = 1; j < COL - 1; j++)
{
if (grid[i][j] != NON)
{
grid[i][j] = list[n];
n++;
}
}
}
// 判断表格中是否有相邻的数字
ok = true;
for (i = 1; i < ROW - 1; i++)
{
for (j = 1; j < COL - 1; j++)
{
n = grid[i][j];
if ((grid[i - 1][j - 1] == n - 1) || ((grid[i - 1][j - 1] == n + 1)) || // 左上
(grid[i - 1][j + 1] == n - 1) || ((grid[i - 1][j + 1] == n + 1)) || // 右上
(grid[i - 1][j] == n - 1) || ((grid[i - 1][j] == n + 1)) ||   // 上
(grid[i][j - 1] == n - 1) || ((grid[i][j - 1] == n + 1)) ||   // 左
(grid[i][j + 1] == n - 1) || ((grid[i][j + 1] == n + 1)) ||   // 右
(grid[i + 1][j] == n - 1) || ((grid[i + 1][j] == n + 1)) ||   // 下
(grid[i + 1][j - 1] == n - 1) || ((grid[i + 1][j - 1] == n + 1)) || // 左下
(grid[i + 1][j + 1] == n - 1) || ((grid[i + 1][j + 1] == n + 1))    // 右下
)
{
ok = false; // 发现任一相邻数则设置失败标记，跳出该轮循环
break;
}
}
if (!ok)   // 如标记为失败，跳出外层循环
break;
}
// 如标记为成功，方案有效，打印输出
if (ok)
{
//PrintGrid(); // 打印输出有效方案
count++;
}
}