EOJ 1120 Peg Game
发布日期:2021-08-13 18:02:28 浏览次数:7 分类:技术文章

本文共 5444 字,大约阅读时间需要 18 分钟。

Peg Game

Time Limit:1000MSMemory Limit:30000KB

Total Submit:224Accepted:86Special Judge

Description

You are given a 7-by-7 board of holes. Some holes are filled with pegs, and some are not. You may jump a peg over
an adjacent peg, as long as the hole the jumping peg lands in is unoccupied. The jumped peg is removed. Your goal
is to leave the board with only one peg in it, and the peg must end up in the specified location.
The board is specified as a 7-by-7 array of characters, with the following meanings:
x : this hole may never be occupied by a peg
e : this hole is initially empty
o : this hole is initially occupied by a peg
E : this hole is initially empty, and the last peg should end here
O : this hole is initially occupied, and the last peg should end here
For example, consider the following board:
x x e e e x x
x x o e e x x
e e o e e e e
e e o O e e e
e e e e e e e
x x e e e x x
x x e e e x x
You can see that there are initially 4 pegs in the board, and the last peg should end up in the middle of the board.
The winning sequence of moves is:
1. (4, 4) to (2, 4)
2. (3, 2) to (3, 4)
3. (2, 4) to (4, 4)
Where coordinates are given as (x, y).

Input

The first line of input is the number of datasets to follow. Each dataset should be processed the same.
The input for each dataset consists of 7 lines; each line consists of 7 characters from the set {x, e, o, E, O}
with blanks between them. You are guaranteed that exactly one 'E' or 'O' will appear, and that two or more 'o' or 'O'
will appear.

Output

For each dataset, output a line containing the data set number. If a sequence of valid moves exists that leaves only
one peg on the board, and leaves that peg in the desired location, print out the sequence of moves, as shown in the
above example. If no sequence exists, print “No solution". Leave a blank line between datasets.

Sample Input

2
x x e e e x x
x x o e e x x
e e o e e e e
e e o O e e e
e e e e e e e
x x e e e x x
x x e e e x x
x x e E e e e
x e e e e e e
e e e o o e e
e e e x e e e
e e e e e e e
e e e e e e e
e e e e e e e

Sample Output

Dataset 1:
1. (4, 4) to (2, 4)
2. (3, 2) to (3, 4)
3. (2, 4) to (4, 4)
Dataset 2:
No solution.

写个BFS吧,就是长了点。。

#include
#include
#include
#include
using namespace std;struct data{ char s[8][8]; int id;};struct point{ int sx,sy,ex,ey;};point p[1000050];int pre[1000050];int ex,ey;int id;int ca = 1;void path(int id){ //printf("id = %d\n",id); if(id)path(pre[id]); if(id)printf("%d. (%d, %d) to (%d, %d)\n",ca ++,p[id].sy + 1,p[id].sx + 1,p[id].ey + 1,p[id].ex + 1);}bool judge(data a){ int cnt = 0; int tx = -1,ty = -1; for(int i = 0;i < 7;i ++){ for(int j = 0;j < 7;j ++){ //printf("%c",a.s[i][j]); if(a.s[i][j] == 'o'){ cnt ++; tx = i; ty = j; } } //printf("\n"); } return cnt == 1 && tx == ex && ty == ey;}bool in(int x,int y){ return x >= 0 && x < 7 && y >= 0 && y < 7;}int main(){ int t; int cc = 1; scanf("%d",&t); getchar(); while(t --){ data tp; char c; for(int i = 0;i < 7;i ++){ for(int j = 0;j < 7;j ++){ //scanf("%c%c",&tp.s[i][j],&c); cin>>tp.s[i][j]; //printf("%c%c",tp.s[i][j],c); if(tp.s[i][j] == 'O'){ ex = i;ey = j; tp.s[i][j] = 'o'; } else if(tp.s[i][j] == 'E'){ ex = i;ey = j; tp.s[i][j] = 'e'; } } } memset(pre,0,sizeof(pre)); id = 0; ca = 1; tp.id = id++; queue
q; bool flag = false; q.push(tp); while(!q.empty()){ tp = q.front(); q.pop(); if(judge(tp)){ flag = true; break; } //printf("id = %d\n",tp.id); data pp = tp; for(int i = 0;i < 7;i ++){ for(int j = 0;j < 7;j ++){ if(tp.s[i][j] == 'o'){ if(in(i - 2,j) && tp.s[i - 1][j] == 'o' && tp.s[i - 2][j] == 'e'){ pp.s[i][j] = 'e'; pp.s[i - 1][j] = 'e'; pp.s[i - 2][j] = 'o'; p[id].sx = i; p[id].sy = j; p[id].ex = i - 2; p[id].ey = j; pp.id = id; //printf("%d %d %d %d\n",p[id].sx,p[id].sy,p[id].ex,p[id].ey); q.push(pp); pre[id ++] = tp.id; } pp = tp; if(in(i,j + 2) && tp.s[i][j + 1] == 'o' && tp.s[i][j + 2] == 'e'){ pp.s[i][j] = 'e'; pp.s[i][j + 1] = 'e'; pp.s[i][j + 2] = 'o'; p[id].sx = i; p[id].sy = j; p[id].ex = i; p[id].ey = j + 2; pp.id = id; //printf("%d %d %d %d\n",p[id].sx,p[id].sy,p[id].ex,p[id].ey); q.push(pp); pre[id ++] = tp.id; } pp = tp; if(in(i + 2,j) && tp.s[i + 1][j] == 'o' && tp.s[i + 2][j] == 'e'){ pp.s[i][j] = 'e'; pp.s[i + 1][j] = 'e'; pp.s[i + 2][j] = 'o'; p[id].sx = i; p[id].sy = j; p[id].ex = i + 2; p[id].ey = j; pp.id = id; //printf("%d %d %d %d\n",p[id].sx,p[id].sy,p[id].ex,p[id].ey); q.push(pp); pre[id ++] = tp.id; } pp = tp; if(in(i,j - 2) && tp.s[i][j - 1] == 'o' && tp.s[i][j - 2] == 'e'){ pp.s[i][j] = 'e'; pp.s[i][j - 1] = 'e'; pp.s[i][j - 2] = 'o'; p[id].sx = i; p[id].sy = j; p[id].ex = i; p[id].ey = j - 2; pp.id = id; //printf("%d %d %d %d\n",p[id].sx,p[id].sy,p[id].ex,p[id].ey); q.push(pp); pre[id ++] = tp.id; } } } } } printf("Dataset %d:\n",cc ++); if(flag)path(tp.id); else printf("No solution.\n"); if(t)printf("\n"); } return 0;}

转载于:https://www.cnblogs.com/eternalLight/archive/2013/02/19/3134483.html

转载地址:https://blog.csdn.net/weixin_30696427/article/details/99382533 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:UILabel 的 宽度和高度是固定的,能根据label 的text 动态设置label的字体吗,让label 的text 能显示下...
下一篇:深入理解计算机系统chapter6

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年02月29日 18时07分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装 2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose 2019-04-21
Java前台显示近20天的东西_第十次课:前台首页设计及显示商品信息 2019-04-21
java开发web网站的路由设计_理解Web路由(浅谈前后端路由与前后端渲染) 2019-04-21
excel如何把顺序倒过来_在excel中怎么使文字颠倒顺序反过来显示呢? 2019-04-21
php正则表达式获取图片路径,php 常用正则表达式实例(图片地址,与指定内容获取)... 2019-04-21
脚本语言php是什么意思,PHP脚本语言 2019-04-21
matlab数学规划模型,数学规划模型 2019-04-21
视频提取音频php,如何提取视频中的音频,从视频文件中提取出音频输出成MP3格式... 2019-04-21
diy.php添加验证码,织梦dedecms自定义表单中加入验证码 2019-04-21
在php脚本中 通过可以获取,在PHP中,可以使用Unix时间戳获取精确的脚本执行时间。... 2019-04-21
s2-045 php exp,S2-045-EXP.py --Struts2任意代码执行漏洞 (S2-045,CVE-2017-5638) 2019-04-21
linux sdk 窗口句柄,Venus: 针对Linux平台上,对常用的系统API进行面向对象的封装SDK。... 2019-04-21
c语言程序设计 科学出版社习题答案,C语言程序设计(科学出版社)第4章 课后习题参考答案.doc... 2019-04-21
c语言 无错 但只运行一半,求哈夫曼编码时程序运行到一半就终止了,编译无错... 2019-04-21
deepin linux 2014安装,2014.2版本的Deepin虚拟机安装浅谈(就是深度Linux) 2019-04-21
android 限速工具,Android下载器之限速篇 2019-04-21
html刷新ajax实现原理,AJAX的原理—如何做到异步和局部刷新 2019-04-21
html中列表菜单加文字请选择,html中下拉菜单 2019-04-21
读书郎平板中android,读书郎学生平板电脑怎么用 使用方法详解【图文】 2019-04-21