【算法】矩阵填数，深度优先搜索（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行之后打个空行好看点 
//    }
}

结果

• 输入一个起始点坐标后输出的方案

• 输出所有起始点的方案个数：