poj A Knight's Journey
이 문제는 바둑판의 모든 점을 두루 훑어보고 기사가 바둑판을 두루 돌아다닐 수 있는지 확인해야 하기 때문에 분명히 DFS 문제입니다. 출력 경로는 반드시 사전순으로 출력해야 합니다. 그러면 우리는 기사의 걷는 방향을 사전순으로 정의해야 합니다.자세한 내용은 아래 코드의dir[8][2] 그룹을 보십시오.
AC 코드입니다.
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,vis[30][30],sum,path[30][2],f;
int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
void dfs(int x,int y)
{
vis[x][y]=1;
sum++;
path[sum][0]=x;
path[sum][1]=y;
if(sum==n*m)
{
for(int i=1;i<=sum;i++)
printf("%c%d",path[i][0]+'A',path[i][1]+1);
printf("
");
f=1;
return ;
}
for(int i=0;i<8;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx<0||yy<0||xx>=n||yy>=m||vis[xx][yy])
continue;
dfs(xx,yy);
if(f)
return;
sum--;
vis[xx][yy]=0;
}
}
int main(void)
{
int t;
scanf("%d",&t);
int k;
for(k=1;k<=t;k++)
{
if(k!=1)
printf("
");
scanf("%d%d",&m,&n);
memset(vis,0,sizeof(vis));
sum=0;
printf("Scenario #%d:
",k);
f=0;
dfs(0,0);
if(!f)
printf("impossible
");
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
