您现在的位置是:首页 > 正文

程序设计实习MOOC/第十五周编程作业/B:A Knight's Journey(TUD Programming Contest 2005, Darmstadt, Germany)

2024-04-01 00:35:02阅读 3
题目:B:A Knight's Journey
总时间限制: 1000ms 内存限制: 65536kB
描述
Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
输入
The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
输出
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
样例输入
3
1 1
2 3
4 3
样例输出
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4


解题思路:深度优先搜索,值得注意的是要按字典序方向,所以八个方向的顺序固定!

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

struct Step
{
    int row;//对应某一行 
    int col;//对应某一列 
    Step(int _r, int _c):row(_r),col(_c){}
};

int p, q, counts, visited[8][8];
bool flag = false;//标识是否有路线

void DFS(queue<Step> s, int k)//分别表示已走过的路线、还有多少个位置没有走过
{
    if(k == 0)//找到路线了,则输出路线,修改标识位 
    {
        flag = true;
        
        cout << "Scenario #" << counts << ":" <<endl;
        while(s.size() != 0)
        {
            Step step = s.front();//从队列(路线)中取出队头元素
            s.pop();
            char alphabet[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 
            'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
            cout << alphabet[step.col]/*输出列号从A开始*/ << step.row + 1;//要加一,因为程序中是从0开始计数,而输出中是以1开始 
        }
        cout <<endl;
        return;
    }
    //来到这里,表明前面没有return,即k不等于0,此时,考察往八个方向走的情况
    Step step = s.back();//读取上一步的位置
    int row, col;
    row = step.row;
    col = step.col;
    
    //由于要字典序输出,所以八个方向顺序一定不能错 
    if(!flag && !visited[row - 1][col - 2] && row - 1 >= 0 && col - 2 >= 0)//当前还未找到一条可行路线且步走法可行 
    {
        visited[row - 1][col - 2] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row - 1, col - 2));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row - 1][col - 2] = 0;//回溯,不走该步,由于我是用s_temp来存储当前步的,
        //所以对于换一条路线,用的s仍是不变的,所以不会有影响 
    }
    
    if(!flag && !visited[row + 1][col - 2] && row + 1 < p && col - 2 >= 0)//当前还未找到一条可行路线且步走法可行
    {
        visited[row + 1][col - 2] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row + 1, col - 2));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row + 1][col - 2] = 0;
    }
    
    if(!flag && !visited[row - 2][col - 1] && row - 2 >= 0 && col - 1 >= 0)//当前还未找到一条可行路线且步走法可行
    {
        visited[row - 2][col - 1] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row - 2, col - 1));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步
         
        visited[row - 2][col - 1] = 0;
    }
    
    if(!flag && !visited[row + 2][col - 1] && row + 2 < p && col - 1 >= 0)//当前还未找到一条可行路线且步走法可行
    {
        visited[row + 2][col - 1] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row + 2, col - 1));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row + 2][col - 1] = 0;
    }
    
    if(!flag && !visited[row - 2][col + 1] && row - 2 >= 0 && col + 1 < q)//当前还未找到一条可行路线且步走法可行
    {
        visited[row - 2][col + 1] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row - 2, col + 1));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row - 2][col + 1] = 0;
    }
    
    if(!flag && !visited[row + 2][col + 1] && row + 2 < p && col + 1 < q)//当前还未找到一条可行路线且步走法可行
    {
        visited[row + 2][col + 1] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row + 2, col + 1));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row + 2][col + 1] = 0;
    }
       
    if(!flag && !visited[row - 1][col + 2] && row - 1 >= 0 && col + 2 < q)//当前还未找到一条可行路线且步走法可行
    {
        visited[row - 1][col + 2] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row - 1, col + 2));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row - 1][col + 2] = 0;
    }
    
    if(!flag && !visited[row + 1][col + 2] && row + 1 < p && col + 2 < q)//当前还未找到一条可行路线且步走法可行
    {
        visited[row + 1][col + 2] = 1;
        queue<Step> s_temp = s;
        s_temp.push(Step(row + 1, col + 2));//将该步加入路线中,形参拷贝传递,所以不同路线之间不会影响 
        DFS(s_temp, k - 1);//继续下一步 
        
        visited[row + 1][col + 2] = 0;
    }  
}

int main()
{
    int n; 
    queue<Step> s;//使用队列存储每一步走到的位置 
    counts = 0;
    cin >> n;
    
    while(counts != n)
    {
        counts++;
        flag = false;
        memset(visited, 0, sizeof(visited));
        cin >> p >> q;
        
        for(int i = 0; i < p; i++)
        {
            for(int j = 0; j < q; j++)
            {
                s.push(Step(i, j));//(i,j)作为起始位置
                visited[i][j] = 1;
                DFS(s, p * q - 1);//还有p*q-1个位置没有走过
                
                visited[i][j] = 0;//回溯,考察下一个起始位置 
                s.pop();//由于s是作为形参复制拷贝传递进DFS去,所以在main函数中的s就只有第一个起始位置,
                //所以这里弹出第一个起始位置即可,s就清空了,方便考察for循环中下一个起始位置
                if(flag)//找到一条路线了,在DFS中已经输出该路线了,跳出循环 
                    break;
            }
            if(flag)//找到一条路线了,在DFS中已经输出该路线了,跳出循环 
                break;
        }
        if(! flag)//for循环结束都没有找到路线,则输出impossible 
            cout << "Scenario #" << counts << ":" <<endl << "impossible" <<endl;
        cout << endl;
    }
    
    system("pause");
    return 0;
}

网站文章

  • java前端显示统计报表数据_强大的报表前端展现功能

    灵活的查询交互报表为用户提供了通用的查询面板用于各种条件过滤,在报表展现界面,用户设定各查询条件的值后点击查询按钮,报表数据便将根据输入的条件值动态查询出相应的结果。形象的图表结合报表以形象美观的图表...

    2024-04-01 00:34:54
  • reverse1

    reverse1

    reverse1思路,ida一些方便的用法

    2024-04-01 00:34:48
  • adb连接真实设备连接不上时或者连接时报adb server is out of date.killing的解决方法

    adb连接真实设备连接不上时或者连接时报adb server is out of date.killing的解决方法

    1.当adb连接真实设备,连接不上时,可能是手机通过usb线连接电脑时没有自动安装驱动,所以手机没有弹出usb调试允许与否的弹窗,这时可以在手机或者电脑端下载个“360手机助手”,手机连接上电脑时,即...

    2024-04-01 00:34:23
  • tmux不能激活conda的原因 - 终端处于conda base环境

    问题描述:想在tmux终端激活conda环境,按照网上的说法退出重激活多次仍然没有效果,最后发现是开启tmux终端时,本身处在了conda的base环境下。解决:退出tmux,退出base环境当终端开...

    2024-04-01 00:34:14
  • 《计算机网络(第7版)-谢希仁》期末考试复习题和答案(总结整理)

    期末复习试题总结 一、选择题。 1、广域网覆盖的地理范围从几十公里到几千公里。它的通信子网主要使用( B )。 A、报文交换技术 B、分组交换技术 C、文件交换技术 D、电路交换技术 2、数据链路层中...

    2024-04-01 00:34:08
  • 【力扣经典面试题150道(java)】28. 找出字符串中第一个匹配项的下标 最新发布

    输入:haystack = “leetcode”, needle = “leeto”输入:haystack = “sadbutsad”, needle = “sad”解释:“leeto” 没有在 “l...

    2024-04-01 00:34:02
  • request的getParameterMap方法

    public class UserServlet extends HttpServlet { public void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException { try { //解决乱码 reques...

    2024-04-01 00:33:39
  • PC软件CPU高定位示例

    PC软件CPU高定位示例

    WINDOWS PC软件CPU高定位示例。

    2024-04-01 00:33:32
  • 7、volatile

    https://www.cnblogs.com/fengzheng/p/9070268.html并发的三个特性并发场景三个特性:原子性、可见性、有序性;只有在满足了这三个特性,才能保证并发程序正确执行,否则会出现各种问题;1、原子性:cas(乐观锁)和atomic*类,可以保证简单操作的原子性,对于一些负责的操作,可以使用synchronized或者各种锁来实现。2、可...

    2024-04-01 00:33:25
  • vite 移动端项目搭建vue3+ts+vant3

    vite 移动端项目搭建vue3+ts+vant3

    这样在代码保存的时候, eslint就会自动检查并修复。(使用vite官方模板),这里使用的是vue-ts版本。属性,设置该属性后,即可在对应的机型上开启适配。也可以添加到package.json中。...

    2024-04-01 00:33:02