`
Jianquan
  • 浏览: 19831 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

UVa 10422 Knights in FEN

    博客分类:
  • UVa
阅读更多
题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1363
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
using namespace std;

struct State
{
	short step,x,y;
	char map[5][5];
};
struct cmp
{
	bool operator () (State a,State b) const
	{
		return memcmp(a.map,b.map,25)<0;
	}
};

char final[5][5]={'1','1','1','1','1','0','1','1','1','1','0','0',' ','1','1','0','0','0','0','1','0','0','0','0','0'};
set<State,cmp> vis;

int try_to_insert(State s)
{
	if(vis.count(s)) return 0;
	vis.insert(s);
	return 1;
}
void solve(State &head)
{
	if(memcmp(head.map,final,sizeof(final))==0)
	{
		printf("Solvable in 0 move(s).\n");
		return;
	}
	queue<State> q;
	q.push(head);
	while(!q.empty())
	{
		int i;
		short dir[8][2]={-1,-2,1,-2,-2,-1,2,-1,-1,2,1,2,-2,1,2,1};
		State cur;
		cur=q.front();
		q.pop();
		if(cur.step>=11)
		{
			printf("Unsolvable in less than 11 move(s).\n");
			return;
		}
		if(memcmp(cur.map,final,sizeof(final))==0)
		{
			printf("Solvable in %d move(s).\n",cur.step);
			return;
		}
		for(i=0;i<8;i++)
		{
			State next=cur;
			next.x=cur.x+dir[i][0];
			next.y=cur.y+dir[i][1];
			if(next.x<0||next.x>4||next.y<0||next.y>5) continue;
			char t=next.map[next.x][next.y];
			next.map[next.x][next.y]=next.map[cur.x][cur.y];
			next.map[cur.x][cur.y]=t;
			next.step++;
			if(try_to_insert(next))
				q.push(next);
		}
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	int i,j,N;
	State head;
	scanf("%d",&N);
	getchar();
	while(N--)
	{
		for(i=0;i<5;i++)
		{
			for(j=0;j<5;j++)
			{
				head.map[i][j]=getchar();
				if(head.map[i][j]==' ')
				{
					head.x=i;
					head.y=j;
				}
			}
			getchar();
		}
		head.step=0;
		vis.clear();
		solve(head);		
	}
	return 0;
}
分享到:
评论

相关推荐

    POLYGON Knights Pack.unitypackage

    POLYGON+-+Knights+Pack.unitypackage 美术资源,还不错

    Knights Landing(KNL)简介

    Intel第二代Xeon Phi产品代号“Knights Landing”(KNL)的架构和技术细节,既可以继续做协处理器,也可以单独做中央主处理器,不再必须有Xeon的支撑,因而更加灵活。采用了14nm新工艺,架构是Silvermont的改进定制版...

    unity中世纪场景人物POLYGON - Knights Pack 1.0.zip

    《Unity中的中世纪场景构建与角色设计:以“Knights Pack 1.0”为例》 Unity3D作为一款强大的跨平台游戏开发引擎,被广泛应用于各种类型的游戏制作,尤其在构建中世纪风格的场景和角色设计方面,其灵活性和表现力更...

    POLYGON - Knights Pack 1.2.7z

    《POLYGON - Knights Pack》是游戏开发领域的一款资源包,版本为1.2,采用7z压缩格式。这个包主要面向使用Unity引擎的开发者,它包含了一系列与骑士主题相关的游戏资源,如角色模型、动画、纹理等,方便开发者快速...

    mighty-knights:强大的骑士

    《mighty-knights:强大的骑士》是一款融合了Capcom的经典游戏元素“骑士团之轮”与“强大的最后一战”的Sega Master System平台游戏。Sega Master System是8位时代的家用游戏机,它拥有丰富的游戏库,吸引了众多玩家...

    Android代码-The Knights of Alentejo

    The Knights Of Alentejo An Android rewrite of a Ludum Dare turn-based adventure game I wrote way back. Guide portuguese knights through a dungeon and kill demons. GooglePlay: ...

    FantasyHorde_Knights.unitypackage

    Knights ready to protect your kingdom! VR ready. Each model has low polygon count and optimized textures. Great for mobile and hordes! (4 unique body textures and a weapons texture with specular and...

    two-knights:Haskell国际象棋

    标题“two-knights:Haskell国际象棋”指的是一个使用Haskell编程语言实现的国际象棋问题,特别关注“两个骑士”的动态。在国际象棋中,骑士是唯一可以走L形路径的棋子,即每次移动两格横向或纵向,然后一格横向或...

    POLYGON Knights - Low Poly 3D Art by Synty - 1.3.unitypackage

    POLYGON Knights - Low Poly 3D Art by Synty - 1.3.unitypackage

    【Unity骑士主题3D美术资源包】POLYGON Knights - Low Poly 3D Art by Synty

    文件名:POLYGON Knights Low Poly 3D Art by Synty v1.5.unitypackage POLYGON Knights - Low Poly 3D Art by Synty 是由 Synty Studios 开发的 Unity 插件,提供了一套风格化的低多边形(Low Poly)骑士主题的 3D...

    knights

    【标题】"knights"可能是指一个与编程相关的项目或者库,主要与JavaScript语言关联。在编程领域,"knights"通常不会作为一个特定的技术术语,但可能是开发者为某个项目或工具选择的命名,可能寓意着代码的守护者、...

    KT.rar_knights_kt_kt java_骑士巡游

    【标签】"knights"代表骑士,"kt"可能是项目或类名的缩写,而"kt_java"则明确了这是使用Java语言实现的。"骑士巡游"是一个典型的图论问题,它属于回溯算法或深度优先搜索(DFS)的应用场景。在这个游戏中,我们需要...

    Guide to Automatic Vectorization with Intel AVX-512 Instructions in Knights Landing Processors - Bonan Zhang - Colfax International, 2016 (Colfax_KNL_AVX512_Guide)-计算机科学

    INTEL AVX-512 INSTRUCTIONSIN KNIGHTS LANDING PROCESSORSBonan ZhangColfax InternationalMay 11, 2016Abstract This publication is part of a developer guide fo-cusing on the new features in 2nd generation...

    Knights-Ascension:Cocos2dx中一个非常无聊的android游戏

    《Knights-Ascension》是一款基于Cocos2d-x框架开发的Android游戏,由开发者Andre Popovitch与他的伙伴Zeph Balsley和Joseph Waldorf共同创作。Cocos2d-x是一个广泛使用的开源游戏引擎,它支持多平台开发,包括iOS、...

    POJ2942-Knights of the Round Table【Tarjan算法】

    POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...

    JS版圆桌骑士(Knights of the round re-edition)完整源代码 v0.1.3

    Knights of the round re-edition DEMO v0.1.3 Source Options: Turbo AutoSkipFrame Mute Pause Flash 0.5x 1x 1.5x 2x 3x 4x How to play: &lt;W S A D&gt; Move &lt;J&gt; Attack &lt;K&gt; Jump &lt;P&gt; Pause Try combo keys to ...

    Knights-开源

    《Knights:开源的图形象棋界面》 在信息技术领域,开源软件的影响力日益增强,它们为用户提供了自由、透明的代码,同时也鼓励了社区协作和创新。Knights,一个专为K桌面环境设计的图形象棋界面,就是这样一个杰出...

    python-knights-travail

    《Python骑士之旅:深入探索"python-knights-travail"》 在编程的世界里,Python是一种强大而易学的语言,广泛应用于数据科学、Web开发、自动化任务等多个领域。"python-knights-travail"项目,从其命名来看,可能...

Global site tag (gtag.js) - Google Analytics