文档章节

poj_2488_A Knight's Journey_骑士周游问题

電泡泡
 電泡泡
发布于 2013/10/09 21:56
字数 773
阅读 64
收藏 0

实在是自己照着模板写一遍不喜欢书上的代码风格就用网上的搜的一份代码

说实话vector用的却是不顺溜

#include <iostream>
#include <stdio.h>
#define two(X) ((ULL)1<<(X))
using namespace std;
typedef unsigned long long ULL;
const int dx[]={2, 1, -1, -2, -2, -1, 1, 2};
const int dy[]={-1, -2, -2, -1, 1, 2, 2, 1};
ULL lim = two(63)-1 + two(63);
int cnt[8][8], NX, NY;
int sign=0;
vector<pair<int, int>>answ, ans;
bool dfs(int x, int y, ULL state){
    if(state==lim){
        answ.push_back(make_pair(x, y));
        sign=1;
        return 1;
    }

    int ct =0;
    int px[9], py[9], id[9];
    for(int i=0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(bx>=0&&nx<NX&&y>=0&&y<NY && !(state&two(nx*NY+ny))){
            px[ct]=nx; py[ct]=ny;
            ct++;
        }
    }
    if(!ct){
        return 0;
    }
    for(int i=0; i<ct; i++)id[i]=i;
    for(int i=0; i<ct; i++){
        for(int j=i+1; h<ct; j++){
            if(cnt[px[id[i]]][py[id[i]]] > cnt[px[id[j]]][py[id[j]]]){
                swap(id[i], id[j]);
            }
        }
    }
    for(int i=0; i<ct; i++){
        if(dfs(px[id[i]]), py[id[i]], state|two(px[id[i]]*NY+py[id[i]])){
            answ.push_back(make_pair(x, y));
            return 1;
        }
    }
    return 0;
}
vector<pair<int ,int>>slove(int NX0, int NY0)
{
    NX=NX0; Ny=NY0;
    answ.claer();
    lim=two(NX*NY-1)-1+two(NX*NY-1);
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            cnt[i][j]=0;
            for(int k=0; k<8; k++){
                int nx=i+dx[k];
                int ny=j+dy[k];
                if(nx>=0 && nx<NX &&ny>=0 && ny<NY){
                    cnt[i][j]++;
                }
            }
        }
    }
    dfs(0, 0, 1);
    return answ;
}
int main()
{
    int t, n, m;
    scanf("%d", &t);
    for(int i=1; i<=t; i++){
        sign=0;
        scanf("%d%d", &n, &m);
        ans=slove(n, m);
        printf("Scenario #%d:\n", i);
        if(sign){
            for(int i=0; i<n*m; i++){
                printf("%c", ans[i]+64);
            }
        }
        else{
            printf("impossible");
        }
        printf("\n");
    }
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAX 27
int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};//下一步的八个方向
int step,zx[MAX],zy[MAX],map[MAX][MAX],mark;//记录已经走过的步数,记录走过的网格的横纵坐标,标记该网格是否走过,记录是否找到路径
int p,q;

int dfs(int i,int j)//深搜函数
{
    if(mark)return 0;//如果已经找到路径 返回
    int x,y;
    zx[step]=i;//记录当前网格的横坐标
    zy[step]=j;//记录当前网格的纵坐标
    step++;
    if(step==p*q)//如果走过的步数等于棋盘上网格的总数
    {
        mark=1;//找到路径
        return 0;//返回
    }
    map[i][j]=1;//标记该网格
    for(int k=0;k<8;k++)
    {
        x=i+dir[k][1];//下一步x
        y=j+dir[k][0];//下一步y,这个地方的x,y的顺序千万别错了,为了保证字典续
        if(map[x][y]==0&&x>0&&x<=p&&y>0&&y<=q)//判断是否走过 判断是否越界
        {
            dfs(x,y);//如果没有走过,没有越界,向下深搜
            step--;//如果返回 步数减一
        }
    }
    map[i][j]=0;//清除该网格的标记
    return 0;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output1.txt","w",stdout);
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>p>>q;
            memset(map,0,sizeof(map));//数组清零
            step=mark=0;
            dfs(1,1);//从(1,1)号网格开始深搜
            cout<<"Scenario #"<<i<<":"<<endl;
            if(mark)
            {
                for(int j=0;j<p*q;j++)
                    printf("%c%d",zy[j]+'A'-1,zx[j]);
                cout<<endl;
            }
            else cout<<"impossible"<<endl;
            if(i!=n)cout<<endl;
        }
    }
    return 0;
}


© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 24
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
poj 2488 A Knight's Journey

dfs 注意字典序输出 1 12 34 3 Sample Output Scenario #1:A1 Scenario #2:impossible Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4 Source [Submit] [Go Back] [Status] [Discuss] /*============......

locusxt
2013/12/19
0
0
acm题目及我的程序(2)——Knight Moves (骑士跳跃)

acm题目,来源 http://acm.zju.edu.cn/show_problem.php?pid=1091 problem statement A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find th......

晨曦之光
2012/03/09
1K
0
POJ 2488 A Knight's Journey 【dfs + 思维】

传送门 // 题意: 给定一个n*m的棋盘, 问是否有一种方式可以使这匹马走遍这个棋盘的每一个点, 有的话打印出路径, 并且字典序要尽可能的小. 思路: 可能难点的地方就是字典序那, 其实不用管,...

anxdada
02/26
0
0
棋盘游戏走完k步还能留在棋盘上的概率

Knight Probability in Chessboard 问题: On an x chessboard, a knight starts at the -th row and -th column and attempts to make exactly moves. The rows and columns are 0 indexed......

叶枫啦啦
01/15
0
0
leetcode 174. Dungeon Game 完美世界秋招编程题2

2017年完美世界秋招的原题。 原题链接:https://leetcode.com/problems/dungeon-game/description/ 骑士救公主,每个格子可能加血也可能减血。而且到达每个格子时的血量必须大于等于1,问骑士...

努力的C
2017/10/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么日志要private static final

private static final Log logger = LogFactory.getLog(SpringProperties.class); 对于使用PMD的任何人来说,如果日志记录器没有声明为静态的和final的,那么这个博客的标题就会出现在PMD错误...

stys35
15分钟前
1
0
基于深度学习模型Wide&Deep的推荐

本实验选用数据为UCI开源数据集,仅用于学习,请勿商用) Wide&Deep推荐算法出自一篇论文《Wide&Deep Learning for RecommenderSystems》,Wide&Deep由两部分组成,分别是Wide和Deep。先来说...

阿里云官方博客
18分钟前
1
0
列出文件目录结构

以下代码可快速列出所有文件夹,子文件夹下文件 用tree /f显示为树形结构 mypath = wsh.exec("cmd /c tree /f " & Chr(34) & mypath & Chr(34)).StdOut.ReadAll 用 dir显示为长文件名结构 my...

tedzheng
20分钟前
1
0
8.05-Win10 的一些个人设置

1、隐藏 Cortana搜索框 右击任务栏 ——> 找到Cortana ——> 里面有三个选项(隐藏;显示Cortana图标;显示搜索框) ——> 选中自己所需样式 2、显示“我的电脑”等按钮 桌面右键 ——> 个性...

静以修身2025
21分钟前
1
0
windows 下 es安装ik后报错无法启动

1、没有安装分词器时可以正常启动 2、在安装分词器后就报错了 错误信息:Exception in thread "main" java.security.AccessControlException: access denied ("java.io.FilePermission" "D...

zhu_kai1
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部