题目: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; }
发表评论
-
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 811题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 723题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1639题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1047题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 873题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 695题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 659题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 763题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 603题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1124题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 879题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 656题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 872题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 787题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 824题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 745题目:http://uva.onlinejudge.org/i ...
相关推荐
POLYGON+-+Knights+Pack.unitypackage 美术资源,还不错
Intel第二代Xeon Phi产品代号“Knights Landing”(KNL)的架构和技术细节,既可以继续做协处理器,也可以单独做中央主处理器,不再必须有Xeon的支撑,因而更加灵活。采用了14nm新工艺,架构是Silvermont的改进定制版...
POLYGON - Knights Pack 1.2.7z
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: ...
knights
这套资源包括中世纪战士、武器、旗帜、建筑等,场景截图可参考博客。喜欢这个风格的朋友,可以查看我的博客,寻找更多优秀资源。
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...
强大的骑士Capcom的“骑士团之轮”与Capcom的“强大的最后一战”相遇-Sega Master System的争夺战。
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...
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
两个骑士
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: <W S A D> Move <J> Attack <K> Jump <P> Pause Try combo keys to ...
python-knights-travail
骑士巡游,是用applet的小游戏,你可以自己测试看下你的显示效果
Knights_pygame
这是由我(Andre Popovitch)和我的朋友Zeph Balsley和Joseph Waldorf在Cocos2d-x中制作的游戏。
语言:English 在lichess.org上翻转骑士...Flip Lichess Knights允许您在lichess.org上下棋时自定义棋盘UI。 默认情况下,巫妖骑士团的骑士朝右。 Flip Lichess Knights允许您切换他们的方向,因此他们可以向右或向左。
在近日举办的国际超级计算机的会议中,Intel公司向外展示了其首款超多的商用芯片产品“ Knights Corner”,这款产品借用了Larrabee架构与万亿级计算研究计划的技术,可以将50个及以上的处理器集成到一块单芯片中,...