POJ-2488-A Knight's Journey
http://poj.org/problem?id=2488
给一个n1*n2的棋盘,从(0,0)出发,每次走日字形,能否不重复的遍历所有的点
用DFS即可,需要注意搜索的方向要按字典序
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n1,n2;
int xx[30],yy[30];
int visit[30][30];
int flag;
int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
int go(int x,int y)
{
if(1<=x&&x<=n1&&1<=y&&y<=n2)
return 1;
return 0;
}
void dfs(int x,int y,int num)
{
int i,xxx,yyy;
xx[num]=x;
yy[num]=y;
if(num==n1*n2)
{
flag=1;
return;
}
for(i=0;i<8;i++)
{
xxx=x+dir[i][0];
yyy=y+dir[i][1];
if(go(xxx,yyy)&&!visit[xxx][yyy]&&!flag)
{
visit[xxx][yyy]=1;
dfs(xxx,yyy,num+1);
visit[xxx][yyy]=0;
}
}
}
int main()
{
int i,k,t;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d",&n2,&n1);
memset(visit,0,sizeof(visit));
visit[1][1]=1;
flag=0;
dfs(1,1,1);
printf("Scenario #%d:\n",k);
if(flag)
{
for(i=1;i<=n1*n2;i++)
printf("%c%d",xx[i]+'A'-1,yy[i]);
}
else
printf("impossible");
printf(k==t?"\n":"\n\n");
}
return 0;
}
分享到:
相关推荐
北大POJ2488-A Knight's Journey 解题报告+AC代码
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
poj-2528 Mayor's posters 测试数据及答案
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
西北工业大学-c语言-POJ-题目及答案-第七季.doc
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ2002-Squares 解题报告+AC代码
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码