热爱互联网

poj 2488 A Knight's Journey

题目地址:http://poj.org/problem?id=2488
给出一个国际棋盘,判断马能否不重复的走过所有格,并记录下其中按字典序排列的第一种路径,马可以从任意一点开始走。。。

注意的是要按字典序遍历,那么方向数组要按一定的顺序(遍历要从行最小的,列最小的开始),,如果马从某一点出发,存在这样一条路径遍历所有格,那么马必然可以 从 (1,1,)开始出也存在这样的路径。所以从(1,1)开始搜索,这样就保证满足的是字典序。
横行为字母,纵行为数字。
代码如下:
dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int dir[8][2]={ {-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1} }; //保证字典序依次搜索
int X,Y; // X为行,Y为列
int vis[30][30],path[100];
int flag,cnt;
void dfs(int r,int c,int dep){
     if(flag)
         return ;
     if(dep==X*Y){
         for(int i=0;i<cnt;i++)
             printf("%c",path[i]);
         puts("");
         flag=1;
         return ;
     }
     for(int i=0;i<8;i++){
         int x=r+dir[i][0],y=c+dir[i][1];
         if(!vis[x][y] && x>=1 && x<=X && y>=1 && y<=Y){
             vis[x][y]=1;
             path[cnt++]=x+'A'-1;
             path[cnt++]=y+'1'-1;
             dfs(x,y,dep+1);
             cnt-=2;
             vis[x][y]=0;
         }
     }
}
int main(){
    int Case;
    scanf("%d",&Case);
    for(int i=1;i<=Case;i++){
        scanf("%d%d",&Y,&X);
        memset(vis,0,sizeof(vis));
        vis[1][1]=1;
        path[0]='A';
        path[1]='1';
        flag=0;
        cnt=2;
        printf("Scenario #%d:n",i);
        dfs(1,1,1);
        if(!flag)
            puts("impossible");
        if(i!=Case)
            puts("");
    }
 
    return 0;
}

3 Comments

  • Posted 20/11/2016 at 11:45 | Permalink

    > Coanupteclly, messages are no longer targeted to services but, rather, to resources. This is the case with REST and WS-RF too I think that in REST, the messages are targeted towards a service, but they are /about/ a resource. Subtle but important difference. That’s why HTTP evolved the Host: request header (sort of) – so that a single service (defined by port 80) can process requests about many resources.

  • Posted 25/11/2016 at 10:30 | Permalink

    It is only bad if the Boy Scouts were used to help Republicans; whom we all know are wicked and vile and make their mothers eat dog food.Who wants to take bets this will be acted upon? I bet no; any takers?

  • Posted 30/12/2016 at 10:39 | Permalink

    Kevin, sorry buddy, I have to disagree with you on this one. This actually could be BO's demise!Did you see this morning that the folks over at PETA are raising a bit of a stink about this? And do you know that they have sent him something akin to a hav-a-heart trap for flies, while telling him he should have been a better example? There's no monkeying around these PETA folks. Once you get on the bad side of these cats, they'll dog you till you die.

Post a Comment

Your email is kept private. Required fields are marked *