`
人生难得糊涂
  • 浏览: 117887 次
社区版块
存档分类
最新评论

poj2488--骑士遍历棋盘

 
阅读更多

题目大意:

就是给一个 p*q的棋盘,一个骑士从任意位置出发,要求遍历棋盘所有的位置(骑士按‘日’字走)。

思路:

把A1这个位置当做起点,然后按字母表方向(题目要求)搜索,如果位置可以走则再从新位置往下走(其实就是深度搜索)。

注意每种情况输出完以后还要输出一个空格。

#include<iostream>
using namespace std;
#define len 30
int p,q;
int tot;
int map[len][len];
int movx[]={-2,-2,-1,-1,+1,+1,+2,+2};
int movy[]={-1,+1,-2,+2,-2,+2,-1,+1};
int prix[len*len];
int priy[len*len];
int get(int x,int y,int num)//tot =p*q  num表示已经走了几个位置了 
{
	//超出棋盘范围 或者 已经走过了
	if(x>q||y>p||x<1||y<1||map[x][y])//
			return 0;
	if(num==tot)
	{
		prix[num]=x;
		priy[num]=y;
		return 1;
	}
	int flag=0;
	for(int i=0;i<8;i++)
	{
		map[x][y]=1;
		flag=get(x+movx[i],y+movy[i],num+1);
		map[x][y]=0;
		if(flag==1)
		{
			prix[num]=x;
			priy[num]=y;
			return 1;
		}
	}

		return 0;
}

int main()
{
	int n;
	
	int i,j,k;
	scanf("%d",&n);
	for(int m=1;m<=n;m++)
	{
		scanf("%d",&p);
		scanf("%d",&q);

		for(i=0;i<len;i++)
		{
			memset(map[i],0,sizeof(map[i]));//初始化棋盘为0
		}
		tot=p*q;
		printf("Scenario #%d:\n",m);
		if(get(1,1,1)==0)
			printf("impossible");
		else
		{
			for(j=1;j<=tot;j++)
			printf("%c%d",prix[j]+64,priy[j]);
		}
		printf("\n");
		printf("\n");
	}
	return 0;
}

 

1
1
分享到:
评论
1 楼 金R在奋斗着 2014-06-24  
   目测刚发呀。

相关推荐

    poj2488——dfs深度优先遍历

    poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历

    POJ2488-A Knight's Journey【骑士游历】

    【标题】"POJ2488-A Knight's Journey【骑士游历】" 【知识点解析】 本题是来自北京大学在线编程平台POJ的一道经典算法题——“骑士游历”。题目要求解决的是一个典型的图论问题,即在国际象棋棋盘上,骑士能否...

    POJ3253-POJ3253-Fence Repair【STL优先队列】

    标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ1129-Channel Allocation【四色定理】

    标题中的“POJ1129-Channel Allocation”是指一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目涉及到“四色定理”,这是图论领域的一个经典问题。 四色定理是图论中的一个重要...

    POJ3020-Antenna Placement

    【标题】"POJ3020-Antenna Placement"是一个经典的计算机编程竞赛题目,源自北京大学的在线评测系统POJ(PKU Online Judge)。这个题目挑战了参赛者在算法设计和实现上的能力。 【描述】"解题报告+AC代码"意味着这...

    poj 1000 - 2000 部分题目 官方分类

    《POJ 1000 - 2000 部分题目 官方分类》 编程竞赛,特别是在线判题系统(如POJ,即Problem Online Judge)中的题目,是提升编程技能和算法理解的重要途径。POJ 1000 - 2000 是一个涵盖广泛的题目区间,包含了大量的...

    魔兽世界终极版POJ的-测试数据

    这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q

    POJ2525-Text Formalization【TrieTree】

    《POJ2525-Text Formalization:深入解析TrieTree》 在计算机科学的世界里,算法和数据结构是解决问题的关键。今天我们要探讨的是一个名为"POJ2525-Text Formalization"的问题,它涉及到一种高效的数据结构——Trie...

    POJ2299-Ultra-QuickSort

    【标题】"POJ2299-Ultra-QuickSort"是北京大学在线判题系统POJ上的一道编程题目,其主要涉及的算法是快速排序(Ultra-QuickSort)。快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    POJ1258-Agri-Net【Prim】

    【标题】"POJ1258-Agri-Net【Prim】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到图论中的一个重要算法——普里姆(Prim)算法。 【描述】"北大POJ1258-...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    POJ3414-Pots

    标题“POJ3414-Pots”是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是算法设计和实现能力,通常涉及计算机科学中的数据结构和算法知识。 解题报告是参赛者在...

    POJ2503-Babelfish

    【标题】"POJ2503-Babelfish"是一个来自北京大学在线判题系统(POJ,Problem Online Judge)的编程题目。该题目要求参赛者编写程序解决特定的算法问题,通过编程语言实现,然后提交代码以供系统自动评测。 【描述】...

    POJ1003-Hangover

    【标题】"POJ1003-Hangover"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这类题目通常要求参赛者编写程序来解决特定的算法问题,以此锻炼和测试编程技能及算法理解能力。 【描述...

    POJ1009-Edge Detection

    【标题】"POJ1009 - 边缘检测" 在计算机图形学与图像处理领域,边缘检测是一项至关重要的技术。北京大学编程平台POJ上的第1009题,"Edge Detection"(边缘检测),旨在让学生通过编程实现对图像进行边缘检测。此题...

    POJ1002-487-3279【Hash+Qsort】

    标题中的"POJ1002-487-3279【Hash+Qsort】"是指一个编程挑战题目,通常在在线编程平台上出现,比如北京大学的Peking Online Judge (POJ)。这个题目结合了哈希表(Hash)和快速排序(Qsort)两种算法来解决问题。哈希...

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

Global site tag (gtag.js) - Google Analytics