绝望求助搜索路径输出
改了七个小时代码
绝望求助！！！
题面之后是我的代码
题目描述
整天待在一个方块里, 骑士感到特别的无聊, 于是, 他决定来一场所走就走的旅行 但他只能走日字, 并且世界是一个不大于8*8的棋盘.你能帮勇敢的骑士制定一个旅行计划吗? 请找出一条路使得骑士能够走遍整个棋盘.骑士可以在任一方块出发或结束
输入
第一行输入一个正整数n, 代表数据组数 对于每组数据, 含有两个正整数p和q(1 <= p*q <= 26), 表示一个p*q的棋盘.每个方块的位置用两个字符表示, 第一个从A开始,代表列, 第二个从1开始,代表行
输出
每组数据的结果首先是一行"Scenario #i:", i是数据序号, 从1开始 然后输出一行, 是字典序第一的可以走遍棋盘的路径, 接着有一个空行 路径应该是连续的依次所走方块的位置 如果不存在这样的路径, 输出"impossible"
样例输入
3
1 1
2 3
4 3
样例输出
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
一段有故事的代码
//一开始我想用DFS搜一遍，但是不会存路径
//于是我用了优先队列BFS？
//试图先用一遍DFS判断是否无解
//然后BFS存路径，还要求字典序最小
//我死就死在字典序最小的这个路径，不会。。。改了七个小时，我快傻了。。。
//各位大佬救救我吧，能帮我过了样例就行
//代码有注释
#include <bits/stdc++.h>
using namespace std;
int n,p,q;
int vis[9][9];
int a[9][9];
struct point
{
int x,y;
point(int xx,int yy){
x=xx;y=yy;
}
};
bool operator < (point a1,point a2){
if(a1.x<a2.x)return 1;
if(a1.x>a2.x)return 0;
return a1.y<a2.y;
}
priority_queue <point> que;//这个我打算存BFS的访问顺序
queue <point> out1;//这个用来输出
void BFS(point a){
vis[a.x][a.y]=1;
que.push(a);
int k=1;
while(!que.empty()&&k<=p*q){
out1.push(que.top());
point b=que.top();
que.pop();
//这下面是一段故事
//骑士走日字，这是BFS搜索的过程
if(b.x-2>=1&&b.y-1>=1&&vis[b.x-2][b.y-1]==0){que.push(point(b.x-2,b.y-1));vis[b.x-2][b.y-1]=1;}
if(b.x-2>=1&&b.y+1<=q&&vis[b.x-2][b.y+1]==0){que.push(point(b.x-2,b.y+1));vis[b.x-2][b.y+1]=1;}
if(b.x-1>=1&&b.y-2>=1&&vis[b.x-1][b.y-2]==0){que.push(point(b.x-1,b.y-2));vis[b.x-1][b.y-2]=1;}
if(b.x-1>=1&&b.y+2<=q&&vis[b.x-1][b.y+2]==0){que.push(point(b.x-1,b.y+2));vis[b.x-1][b.y+2]=1;}
if(b.x+1<=p&&b.y-2>=1&&vis[b.x+1][b.y-2]==0){que.push(point(b.x+1,b.y-2));vis[b.x+1][b.y-2]=1;}
if(b.x+1<=p&&b.y+2<=q&&vis[b.x+1][b.y+2]==0){que.push(point(b.x+1,b.y+2));vis[b.x+1][b.y+2]=1;}
if(b.x+2<=p&&b.y-1>=1&&vis[b.x+2][b.y-1]==0){que.push(point(b.x+2,b.y-1));vis[b.x+2][b.y-1]=1;}
if(b.x+2<=p&&b.y+1<=q&&vis[b.x+2][b.y+1]==0){que.push(point(b.x+2,b.y+1));vis[b.x+2][b.y+1]=1;}
}
}
void DFS(int x,int y,int k){
//第二段故事开始了
//DFS用于判断是否有解
//因为我根本不会用DFS存字典序第一的路径啊啊
if(a[x][y]<=k)return;
if(k>=p*q){return;}
a[x][y]=k;
if(x-2>=1&&y-1>=1)DFS(x-2,y-1,k+1);
if(x-2>=1&&y+1<=q)DFS(x-2,y+1,k+1);
if(x-1>=1&&y-2>=1)DFS(x-1,y-2,k+1);
if(x-1>=1&&y+2<=q)DFS(x-1,y+2,k+1);
if(x+1<=p&&y-2>=1)DFS(x+1,y-2,k+1);
if(x+1<=p&&y+2<=q)DFS(x+1,y+2,k+1);
if(x+2<=p&&y-1>=1)DFS(x+2,y-1,k+1);
if(x+2<=p&&y+1<=q)DFS(x+2,y+1,k+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p>>q;
for(int j=1;j<=p;j++)for(int k=1;k<=q;k++)a[j][k]=99999;//赋初值，没搜到就是无解的
cout<<"Scenario #"<<i<<":"<<endl;
DFS(1,1,0);
for(int x=1;x<=p;x++){
for(int y=1;y<=q;y++){
if(a[x][y]==99999){
cout<<"impossible"<<endl<<endl;
goto cc;//无解就直接开始下一组测试点
}
}
}
BFS(point(1,1));
for(int k=0;k<p*q;k++){
cout<<char('A'+out1.front().x-1)<<out1.front().y;
out1.pop();//我打算输出字典序第一的路径，但是不会
}
cc:;
cout<<endl<<endl;
}
}
加载中...