09-11 18:50 南京林业大学 算法工程师 发布于江苏
关注
例题9.3A Knight's Jour
//DFS不难，想想也就能想明白了。但是要注意很多细节：每次都只是对当前情况做出改变，x\y坐标要重新定义新的
#include
#include
using namespace std;
int p;//行数
int q;//列数
bool visit[27][27];
//int direction[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
int direction[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//先数字方向，后字母方向
bool DFS(int i,int j,int step,string str)//i\j先行后列
{
if(step==q*p)
{
cout<
}
else
{
for(int ii=0;ii<8;ii++)
{
int ni=i+direction[ii][0];//i+=direction[ii][0];不能写成这样。因为该方法只对当前情况进行改变，直接修改i、j会对所有情况造成影响
int nj=j+direction[ii][1];//j+=direction[ii][1];
char col='A'+nj-1;//
char row='1'+ni-1;//
if(ni<1||ni>p||nj<1||nj>q||visit[ni][nj]==true)continue; //ninj
visit[ni][nj]=true;//仅仅是当前情况要修改 ninj
if(DFS(ni,nj,step+1,str+col+row))//ninj
{
return true;
}
visit[ni][nj]=false;//算过之后就到下一种情况了，还要改回来 ninj
}
}
return false;
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p>>q;
memset(visit,false,sizeof(visit));
cout<<"Scenario #"<
if(DFS(1,1,1,"A1")==false)
cout<<"impossible"<
}
}
#include
#include
using namespace std;
int p;//行数
int q;//列数
bool visit[27][27];
//int direction[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
int direction[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//先数字方向，后字母方向
bool DFS(int i,int j,int step,string str)//i\j先行后列
{
if(step==q*p)
{
cout<
}
else
{
for(int ii=0;ii<8;ii++)
{
int ni=i+direction[ii][0];//i+=direction[ii][0];不能写成这样。因为该方法只对当前情况进行改变，直接修改i、j会对所有情况造成影响
int nj=j+direction[ii][1];//j+=direction[ii][1];
char col='A'+nj-1;//
char row='1'+ni-1;//
if(ni<1||ni>p||nj<1||nj>q||visit[ni][nj]==true)continue; //ninj
visit[ni][nj]=true;//仅仅是当前情况要修改 ninj
if(DFS(ni,nj,step+1,str+col+row))//ninj
{
return true;
}
visit[ni][nj]=false;//算过之后就到下一种情况了，还要改回来 ninj
}
}
return false;
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p>>q;
memset(visit,false,sizeof(visit));
cout<<"Scenario #"<
if(DFS(1,1,1,"A1")==false)
cout<<"impossible"<
}
}
全部评论
相关推荐
查看14道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
远景一面22人在聊 点赞 评论 收藏
分享
点赞 评论 收藏
分享