poj-2488 a knight's journey(搜索…
2018-08-21 05:28:32来源:博客园 阅读 ()
Time limit1000 ms
Memory limit65536 kB
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
Output
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<iostream> #include<algorithm> #include<cstring> #include<sstream> #include<cmath> #include<cstdlib> #include<queue> #include<stack> using namespace std; #define PI 3.14159265358979323846264338327950 int path[100][2],vis[100][100],p,q,cnt; bool flag; int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; bool judge(int x,int y) { if(x<=p && x>=1 && y<=q && y>=1 && !vis[x][y] ) return true; return false; } void dfs(int r,int c,int step) { if (flag == false) { path[step][0]=r; path[step][1]=c; } if(step==p*q) { flag=true; return ; } for(int i=0;i<8;i++) { int nx=r+dx[i]; int ny=c+dy[i]; if(judge(nx,ny)) { vis[nx][ny]=1; dfs(nx,ny,step+1); vis[nx][ny]=0; } } } int main() { int i,t,cas=0; cin>>t; while(t--) { flag=0; cin>>p>>q; memset(vis,0,sizeof(vis)); vis[1][1]=1; dfs(1,1,1); printf("Scenario #%d:\n",++cas); if(flag) { for(i=1;i<=p*q;i++) { printf("%c%d",path[i][1]-1+'A',path[i][0]); } } else printf("impossible"); printf("\n"); if(t!=0) printf("\n"); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 洛谷P1164->小A点菜 2020-05-18
- 表达式·表达式树·表达式求值 2020-04-29
- STL之<string> 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash