knight5.c

《数据结构-使用C语言》第三版

//骑士巡游问题
#include<stdio.h>
#define MAX 20

int n, m, curr_x, curr_y, step, dir;
int val[8][2]={{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1}};
int chess[MAX][MAX];//, direction[MAX][MAX], last_dir[MAX*MAX];
long cin;
int main()
{
	int i,j;
    int travel(int x, int y);
	printf("Input:");
	scanf("%d%d",&n,&m);
	printf("Input(i,j):");
	while(scanf("%d%d",&curr_x,&curr_y)!=EOF)
	{
		if(curr_x<0 || curr_y<0)break;
		
		//dir=0;
		step=1;
		cin=0;
		
		for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			chess[i][j]=-1;
			//direction[i][j]=0;
		}
		chess[curr_x][curr_y]=1;
		travel(curr_x, curr_y);
		printf("%ld\n",cin);
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			printf("%3d",chess[i][j]);
			printf("\n");
		}
		printf("Input(i,j):");
	}
	return 0;
}/*
int travel(int x, int y)
{
    int i,j,q;
	int tx, ty;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(chess[i][j]>step) chess[i][j]=-1;
    step++;
	chess[x][y]=step;
	
	cin++;
	
    for(q=0;q<8;q++)
    {
        tx=x+val[q][0];
		ty=y+val[q][1];
		if(tx>=0 && tx<n && ty>=0 && ty<m && chess[tx][ty]<0)travel(tx,ty);
    }
    return;
}
void travel(int p,int r)   //DFS
{
    int i,j,q;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(f[i][j]>r) f[i][j]=0;
    r++;
    i=((p-1)/n)+1;
    j=((p-1)%n)+1;
	
	f[i][j]=r;
	
	fgf++;
	
    for(q=1;q<=m;q++)
    {
        i=((q-1)/n)+1;
        j=((q-1)%n)+1;
        if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r);
    }
    return;
}
 dir_x[]={1,1,1,0,0,-1,-1,-1};   
  dir_y[]={-1,1,0,-1,1,-1,1,0};   
  int   p=0;   
  path_x[],path_y[]   save   the   path   of   horse.   
  board[][]   as   chess   board.   
    
  void   trace(int   i,int   j){   
          for(int   k=0;k<8;k++){   
            if(inboard(i+dir_x[k],j+dir_y[k])   
                if(board[i+dir_x[k]][j+dir_y[k]]==0){   
                      board[i+dir_x[k]][j+dir_y[k]]=1;   
                      path_x[p]=i;path_y[p]=j;   
                      p++;   
                      trace(i+dir_x[k],j+dir_y[k]);   
                      p--;   
                      path_x[p]=0;path_y[p]=0;   
                      board[i+dir_x[k]][j+dir_y[k]]=0;   
                }   
          }   
  }   */

int travel(int x, int y)  //递归 
{
	int i;
	int tx, ty;
	cin++;
	if(step>=n*m)return 1;
	
	step++;
	chess[x][y]=step;
	for(i=0;i<8;i++)
	{
		tx=x+val[i][0];
		ty=y+val[i][1];
		if(tx>=0 && tx<n && ty>=0 && ty<m && chess[tx][ty]<0)
		{
			if(travel(tx,ty))break;
			chess[tx][ty]=step;
		}
	}
	if(i>=8)
	{
		chess[x][y]=-1;
		step--;
		return 0;
	}
}