黄道益官网,玉血晗霜玉帘,开心宝贝之美食大作战
time limit1000 ms
memory limit65536 kb
input
output
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"); } }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论