题意:给你一定的格子的棋盘,一匹马是否可以遍历完全整个棋盘
1 #include<stdio.h>
2 #include<string.h>
3 const int MAXN=30;
4
5 //国际象棋纵是数字,横是英文
6 struct Node//用于最后字典序输出
7 {
8 int x,y;
9 }node[MAXN];
10
11 int t1[]={-1,1,-2,2,-2,2,-1,1};
12 int t2[]={-2,-2,-1,-1,1,1,2,2};
13 int vis[MAXN][MAXN];
14
15 int q,p;
16 int flag;
17
18 void DFS(int row,int col,int step)
19 {
20 if(flag) return ;
21 if(step==p*q)
22 {
23 flag=1;
24 return ;//遍历结束
25 }
26 if(row<0 || row >=p || col<0 || col>=q) return;
27 if(vis[row][col]) return ;
28
29 node[step].x=row;
30 node[step].y=col;
31 vis[row][col]=1;
32 for (int i=0;i<8;i++)//八个方向
33 {
34 if(!vis[row+t1[i]][col+t2[i]])
35 DFS(row+t1[i],col+t2[i],step+1);
36 }
37 vis[row][col]=0;
38
39 }
40
41 int main()
42 {
43 int T;
44 int cas=1;
45 scanf("%d",&T);
46 while(T--)
47 {
48 memset(vis,0,sizeof(vis));
49 flag=0;
50 scanf("%d%d",&p,&q);
51 DFS(0,0,0);
52 printf("Scenario #%d:\n",cas++);
53 if(!flag) printf("impossible\n");
54 else
55 {
56 for (int i=0;i<p*q;i++)
57 {
58 printf("%c%d",node[i].y+'A',node[i].x+1);
59 }
60 printf("\n");
61 }
62 printf("\n");
63 }
64 return 0;
65 }
今天又把这道题重新做了一遍,搜索现在依旧很弱,这么简单的一个搜索都要调试半天找错误,后来才发现原来是忘记提前跳出了,当flag=1的时候说明已经找到额
第二个问题就是字典序搜索啦,由于国际象棋是列为字母,横为数字,所以他的字典树是
int row[]= {-1,1,-2,2,-2,2,-1,1};
int col[]= {-2,-2,-1,-1,1,1,2,2};
#include<stdio.h>
#include<string.h>
const int MAXN=40;
int vis[MAXN][MAXN];
int row[]= {-1,1,-2,2,-2,2,-1,1};
int col[]= {-2,-2,-1,-1,1,1,2,2};
struct Node
{
int x,y;
} node[MAXN];
int flag;
int p,q;
void DFS(int i,int j,int cur)
{
if(flag) return ;
if(cur==p*q)//这里也是问题,老是无法确定边界
{
flag=1;
node[cur].x=i;
node[cur].y=j;
return ;
}
node[cur].x=i;
node[cur].y=j;
for(int k=0; k<8; k++)
{
int row_vis=row[k]+i;
int col_vis=col[k]+j;
if(row_vis>=1 && row_vis<=p && col_vis>=1 && col_vis<=q && vis[row_vis][col_vis]==0)
{
vis[row_vis][col_vis]=1;
DFS(row_vis,col_vis,cur+1);
vis[row_vis][col_vis]=0;
}
}
}
int main()
{
int i,j;
int T;
int cas=1;
scanf("%d",&T);
while(T--)
{
flag=0;
memset(vis,0,sizeof(vis));
scanf("%d%d",&p,&q);
for(i=1; i<=p; i++)
{
for(j=1; j<=q; j++)
{
if(flag) break;
vis[i][j]=1;
DFS(i,j,1);
vis[i][j]=0;
}
if(flag) break;
}
printf("Scenario #%d:\n",cas++);
if(!flag) printf("impossible");
else
{
for(i=1; i<=q*p; i++)
{
printf("%c%d",node[i].y+'A'-1,node[i].x);
}
}
printf("\n\n");
}
return 0;
}