POJ_2488——骑士遍历棋盘,字典序走法
2024-09-01 07:50:21
Description
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?
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.
Input
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, . . .
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, . . .
Output
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.
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.
Sample Input
3
1 1
2 3
4 3
Sample Output
Scenario #1:
A1 Scenario #2:
impossible Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
//lexicographically first path
//题目output中出现了以上几个单词
//就是说骑士的移动步子是按照字典顺序来排列的
//首先对列进行排序较小的在前面,然后按行进行排序也是较小的在前面
//我构造的xy坐标是按照SDL中的图形坐标,x往下递增,y往右递增
//转换成数学上的xy坐标就要先对列x做排序然后再对行y做排序
int dirx[]={-,-,-,-,,,,};
int diry[]={-,,-,,-,,-,}; int T,p,q,mark[][];
std::string way;
bool DFS(int x,int y,int step)
{
if(step==p*q)
{
return true;
}
for(int i=;i<;i++)
{
int dx=x+dirx[i];
int dy=y+diry[i];
if((dx>= && dx<=q) && (dy>= && dy<=p) && mark[dx][dy]!=)
{
mark[dx][dy]=;
//当找到路径才会插入操作,所以在main函数循环中不需要清空string
if(DFS(dx,dy,step+))
{
//在第0个位置插入1个字符
//先插入数字然后再插入字母,否则顺序颠倒
way.insert(,,dy+'');
way.insert(,,dx+'A'-);
return true;
}
mark[dx][dy]=;
}
}
return false;
}
int main()
{
scanf("%d",&T);
for(int i=;i<=T;i++)
{
scanf("%d%d",&p,&q);
way.clear();//每次都要清空string
bool find=false;
for(int x=;x<=q && !find;x++)
{
for(int y=;y<=p;y++)
{
memset(mark,,sizeof(mark));
mark[x][y]=;
if(DFS(x,y,))
{
//找到的话插入起始位置
way.insert(,,y+'');
way.insert(,,x+'A'-);
find=true;
break;
}
}
}
std::cout<<"Scenario #"<<i<<":"<<std::endl;
if(find)
{
//整体输出就行
std::cout<<way<<std::endl<<std::endl;
}
else
printf("impossible\n\n");
}
return ;
}
最新文章
- ubuntu 14.04安装右键打开终端功能
- 【ASP.NET Identity系列教程(一)】ASP.NET Identity入门
- 【JSP】自定义标签开发入门
- 【C#】【MySQL】C# 查询数据库语句@Row:=@Row+1
- 一个HTML5老兵坦言:我们真的需要“小程序”么?
- node socket onmessage
- Ruby on Rails Tutorial 第四章 Rails背后的Ruby 之 字符串
- iOS 容易引“起循环引用”的三种场景
- servlet生成验证码
- JavaIO
- selenium常用的模块
- FreeMarker案例
- iOS- 利用AFNetworking(AFN) - 实现文件断点下载
- 遇到以前跑一次却没问题的问题,直接maven install 再跑
- echarts实现环形图
- USB学习笔记连载(七):CY7C68013A 无法识别的可能原因
- css抠图之background-position-背景定位
- Deep Learning基础--各个损失函数的总结与比较
- 【BZOJ】1058: [ZJOI2007]报表统计(splay+set)
- 计蒜客 A2232.程序设计:蒜厂年会-单调队列(双端队列(STL deque)实现)滑窗维护最小前缀和