C - 搜索
2024-10-15 22:54:36
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit Status
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, . . .
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.
#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 经典的DFS,大概题意就是让骑士走遍棋盘的所有格子。一路走到黑,看这条路能不能使骑士把格子都走完。
#include<cstdio>
#include<string.h>
using namespace std;
int vis[][];
char str[];
int s[][]={-,-,-,,-,-,-,,,-,,,,-,,};//这种处理方式很常用的,要记住,即骑士当前所在位置的周围所能走到的位置
int p,q;
int dfs(int x,int y,int sum,int cnt)
{
if(sum==p*q) return ;//sum是记录走过的格子
int x1,y1;
for(int i=;i<;i++)
{
x1=x+s[i][];
y1=y+s[i][];
if(x1>=&&x1<q&&y1>=&&y1<p&&!vis[x1][y1])//边界条件及判断是否访问过吗
{
vis[x1][y1]=;
str[cnt+]=x1+'A';//开一个str数组,用来记录
str[cnt+]=y1+'';
if(dfs(x1,y1,sum+,cnt+))//记得这里要写成sum+1,cnt+2
return ;
vis[x1][y1]=;//回溯
}
}
return ;
}
int main()
{
int t;
scanf("%d",&t);
for(int i=;i<=t;i++)
{
scanf("%d %d",&p,&q);
memset(vis,,sizeof(vis));
memset(str,,sizeof(str));
str[]='A';
str[]='';
vis[][]=;
if(dfs(,,,)){
printf("Scenario #%d:\n",i);
for(int j=;j<strlen(str);j++)
printf("%c",str[j]);
printf("\n\n");//记得每组数据输出后,有个空行
}
else{
printf("Scenario #%d:\n",i);
printf("impossible\n\n");
}
}
return ;
}
最新文章
- AndroidStudio开发环境配置-Windows
- git push 报错!!!!
- servlet生命周期与工作原理
- Linux vagrant+virtualbox环境搭建步骤
- Java基础毕向东day05 对象与对象的区别,匿名内部类,函数的执行流程。
- android 的通知管理
- 用C#来查看电脑硬件和系统信息
- InstallShield打包
- 阿里的dubbo 到底是用来干嘛的?
- 30分钟学会使用Spring Web Services基础开发
- springboot情操陶冶-web配置(二)
- vue 3.0的搭建
- Fetch使用
- C语言进阶--Day2
- Jquery on方法绑定事件后执行多次
- java反编译工具cfr
- 前端网页、php与mysql数据库字符编码(解决中文等乱码问题)
- ROR中h()方法和sanitize的区别及Html Filter
- UIScrollView原理
- ArchLinux 下 virtualbox 报错 libQtCore.so.4: cannot open shared object file