【算法】矩阵填数，深度优先搜索（DFS），Pascal改C语言
面向对象的上机实验
题目
以下列方式向 5*5 矩阵中填入数字。设数字i（1=<i<=25），则数字i+1 的坐标位置应为（E, W）。（E, W）可根据下列关系由（x，y）算出：
1）（E, W）=（x±3，y）
2）（E, W）=（x，y±3）
3）（E, W）=（x±2，y±2）
求解问题如下：
编写一个程序，当数字1被指定于某个起始位置时，列举出其它24个数字应在的位置；列举该条件下的所有可能方案。
参考答案
网上搜索到数学奥赛中本题的Pascal代码
来自http://blog.sina.com.cn/s/blog_1317189490102vp1k.html
Program lx9_1_3;
uses crt;
const n=5;
d:array[1..8，1..2] of shortint=((3，0)，(-3，0)，(0，3)，(0，-3)，
(2，2)，(2，-2)，(-2，2)，(-2，-2));
var x0，y0:byte;
a:array[1..n，1..n] of byte;
total:longint;
procedure print;
var i，j:integer;
begin
inc(total);
gotoxy(1，3);
writeln(‘[‘，total，‘]‘);
for i:=1 to n do
begin
for j:=1 to n do
write(a[i，j]:3);
writeln;
end;
end;
procedure try(x，y，k:byte);
var i，x1，y1:integer;
begin
for i:=1 to 8 do
begin
x1:=x+d[i，1];y1:=y+d[i，2];
if (x1>0) and (y1>0) and (x1<=n)
and (y1<=n) and (a[x1，y1]=0) then
begin
a[x1，y1]:=k;
if k=n*n then print
else try(x1，y1，k+1);
a[x1，y1]:=0;
end;
end;
end;
begin
clrscr;
write(‘x0，y0=‘);readln(x0，y0);
fillchar(a，sizeof(a)，0);
total:=0;a[x0，y0]:=1;
try(x0，y0，2);
writeln(‘Total=‘，total);
writeln(‘Press any key to exit..。‘);
repeat until keypressed;
end.自改C语言代码
运用了深度优先搜索算法。
可以输入一个起始位置的坐标后，列举出所有可能方案和方案个数。
也可以输出所有初始点方案的个数。
#include <stdio.h>
#define N 5//格子行列数
int next[8][2]={{3,0},{-3,0},{0,3},{0,-3},{2,2},{2,-2},{-2,2},{-2,-2}};//下一步变换的位移
int x0,y0;//输入的初始坐标
int matrix[N][N];//存储nxn矩阵中的数字
int total;//方案数量
//打印一个矩阵的函数
void printMatrix(){
int i,j;
total+=1;//出来一次结果，就打印一次，方案数+1
printf("第%d种方案:\n",total);
for(i=0;i<N;i++){
for(j=0;j<N;j++){
printf("%4d",matrix[i][j]);//%4d表示输出宽度为4，且右对齐
}
printf("\n");
}
printf("\n");
}
////每个初始点都输出方案的个数的话就不把每个方案打印出来了，太占地方
//void printMatrix(){
// int i,j;
// total+=1;//出来一次结果，就打印一次，方案+1
//}
//主要函数,(x,y)是矩阵内坐标,k是第几个数字
void try(x,y,k){
int i,x1,y1;//x1,y1是本次要找的坐标
//将8个位移都试一遍
for(i=0;i<8;i++){
x1=x+next[i][0];
y1=y+next[i][1];
//如果该位置不超过边界且没有数字，则方案可行，把数字装进这个位置
if((x1>-1)&&(y1>-1)&&(x1<N)&&(y1<N)&&(matrix[x1][y1]==0)){
matrix[x1][y1]=k;
//如果k=25即已经搜索完，可以打印了
if(k==N*N)
printMatrix();
//如果还没到25，就继续搜索下一个位置
else
try(x1,y1,k+1);
//本次打印完/本次搜索尝试到死路，回溯到上一节点去往另一分支前，将这一节点清零
matrix[x1][y1]=0;
}
}
}
int main()
{
//输入坐标
printf("请输入第一个数的坐标（逗号间隔）：");
scanf("%d,%d",&x0,&y0);
//矩阵整体清0（第一条在dev-c++可以跑,vc++不行，还是用老办法）
//memset(matrix, 0, sizeof(matrix));
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
matrix[i][j]=0;
}
}
//数据初始化，运行
total=0;//方案数为零
x0-=1;y0-=1;//用户输入坐标从1开始，c语言数组从0开始
matrix[x0][y0]=1;//第一个位置赋值1
try(x0,y0,2); //从数字2开始放置
printf("总共有%d种摆放方案\n\n",total);
// //每个初始点都输出方案的个数
// int m,n;
// for(m=0;m<5;m++){
// for(n=0;n<5;n++){
// x0=m;y0=n;
// //矩阵整体清0
// int i,j;
// for(i=0;i<N;i++){
// for(j=0;j<N;j++){
// matrix[i][j]=0;
// }
// }
// total=0;//每次节点前方案数清零
// matrix[x0][y0]=1;//第一个位置赋值1
// try(x0,y0,2); //从数字2开始放置
// printf("数字1被指定于(%d,%d)有%d种方案\n",m+1,n+1,total);
// }
// printf("\n");//每5行之后打个空行好看点
// }
}结果
- 输入一个起始点坐标后输出的方案
- 输出所有起始点的方案个数：
