百度之星试题每周一练

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛。他所考试的题目,全部都是算法的题目。

鄙人虽然是一个.net程序员,在工作之余,喜爱算法。 这个问题非常的巧,故而分享给大家,我想到一种超简单方法,提供大家,希望对大家起了一个开阔思路的作用。

首先,题意是这样的:

八方块移动游戏要求从一个含 8 个数字 (用 1-8 表示) 的方块以及一个空格方块 (用 0 表示) 的 3x3 矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动,在四个角落上有 2 个方向可移动,在其他位置上有3 个方向可移动。例如,假设一个 3x3 矩阵的初始状态为: 

8 0 3
2 1 4
7 6 5

目标状态为: 

1 2 3
8 0 4
7 6 5

则一个合法的移动路径为:

8 0 3 8 1 3 8 1 3 2 1 3 1 2 3

2 1 4 => 2 0 4 => 8 0 4 => 8 0 4 

7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5

另外,在所有可能的从初始状态到目标状态的移动路径中,步数最少的路径被称为最短路径;在上面的例子中,最短路径为 3 。如果不存在从初试状态到目标状态的任何路径,则称该组状态无解。 请设计有效的(细节请见评分规则)算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径,并用源代码实现。
输入数据:
程序需读入已被命名为 start.txt 的初始状态和已被命名为 goal.txt 的目标状态,这两个文件都由 9 个数字组成( 0 表示空格, 1-8 表示 8 个数字方块),每行 3 个数字,数字之间用空格隔开。
输出数据:
如果输入数据有解,输出一个表示最短路径的非负的整数;如果输入数据无解,输出 -1 。
自测用例:
如果输入为: start.txt 和 goal.txt ,则产生的输出应为:

又例,如果用
7 8 4
3 5 6
1 0 2
替换 start.txt 中的内容,则产生的输出应为:
17

对于这道题,我思考的思路是这样子的

把每个0-8 的数字,等价于相应横坐标与横坐标的格式例如用一个词典的格式为{7,"0-0"},{8,"0-1"},{4,“0-2”}把两个词典键相等的值,在比较于i,j的值。

相应伪代码如下:

基于这样的思路我们写出的源代码如下所示了:

1 int[,] a1 = new int[3,3]
 2                             {
 3                                 {7 ,8, 4 },
 4                                 {3, 5, 6 },
 5                                 {1, 0, 2}
 6                             };
 7             int[,] bInts = new int[3,3]
 8                                {
 9                                    {1 ,2 ,3},
10                                    {8 ,0 ,4},
11                                    {7, 6, 5}
12                                };
13             int count = 0;
14
15             count = 0;
16             Dictionary<int, string> aList = new Dictionary<int, string>();
17             Dictionary<int, string> bList = new Dictionary<int, string>();
18             for (int i = 0; i < 3; i++)
19             {
20                 for (int j = 0; j < 3; j++)
21                 {
22                     aList.Add(a1[i,j], i.ToString() + "-" + j.ToString());
23                     bList.Add(bInts[i,j], i.ToString() + "-" + j.ToString());
24                     Console.WriteLine();
25
26                     count++;
27
28                 }
29                 Console.WriteLine();
30             }
31             int sum = 0;
32             for (int i = 0; i < 8; i++)
33             {
34                 string aS = aList[i];
35                 string bS = bList[i];
36
37                 sum = sum + Math.Abs(Convert.ToInt32(aS.Split('-')[0]) - Convert.ToInt32(bS.Split('-')[0]));
38                 sum = sum + Math.Abs(Convert.ToInt32(aS.Split('-')[1]) - Convert.ToInt32(bS.Split('-')[1]));
39             }
40             Console.WriteLine(sum+ 1);
41             Console.ReadKey();

这样的思想可能从数学角度得以证明,但纯编程角度,没有深入实质,再就是任何变化,都有解。。。。。。。。。。。这是为何?恳请网友们斧正,最好给出正派解法。我这是旁门左道。

时间: 2024-02-08 07:59:33

百度之星试题每周一练的相关文章

一道百度之星编程大赛题的随笔联想·(2)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 下面介绍解法二了.  解法二,是抓小放大.  由小及大.首先,说一说我分析的思路吧.  第一步,还是判断i是不小于i/2,以此循环了.  第二步,是不是判断此范围的值的累加是不是等于相应某个值. 第三步,

一道百度之星编程大赛题的随笔联想·(1)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,看题目是那样的: 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列. 输入数据:一个正整数,以命令行参数的形式提供给程序. 输出数据:在标准输出上打印出符合题目描述的全部正

由一道百度之星题目写起 谈谈编程中的分类的思想

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个非主流的.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 更重要想谈一谈算法中的分治算法. 首先,题目是那样的: 请编写程序,找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小. 对一个正整数n,如果n在数据文件中某行的两个正

10年百度之星编程赛复赛题目(蜗牛)求答案代码

问题描述 10年百度之星编程赛复赛题目(蜗牛)求答案代码 ?一只蜗牛某天早晨掉进了深为L尺的井中.蜗牛每天白天可以向上爬若干尺,晚上休息时会向下滑若干尺.蜗牛一旦 到达井口或井底,便不再下滑.假设蜗牛每天向上爬的尺数均为不超过10的正整数,而下滑的尺数为不超过5的正整数.蜗牛在第N天白天里(含第N天白天结束时)爬出了井,你的任务是统计有多少种可能的爬升/下滑情况.对于两种爬升/下滑情况,当存在对应的白天上爬或者晚上下滑的尺数不同时,即视为不同的情况.输入格式第一行:井深L.其中L为正整数,且L<

面试经之一道淘汰85%面试者的百度开发者面试题

本文在再次更新,感谢@PhoneGap提供另一中解题思路,,感觉那个方法也挺好的,大家可以看一下第三种解决方案.. 刚在网上看到一篇文章,标题为 一道淘汰85%面试者的百度开发者面试题,感觉好难的样子,就默默的进去看了一下,首先来看一下原题吧. 题目描述: 依序遍历0到100闭区间内所有的正整数,如果该数字能被3整除,则输出该数字及'*'标记:如果该数字能被5整除,则输出该数字及'#'标记:如果该数字既能被3整除又能被5整除,则输出该数字及'*#'标记. 提示: 这道看似非常简单的题目,却潜藏着

2016&quot;百度之星&quot; - 初赛(Astar Round2B)解题报告

此文章可以使用目录功能哟↑(点击上方[+]) 被自己蠢哭,去年还能进一下复赛,今年复赛都没戏了... 链接→2016"百度之星" - 初赛(Astar Round2B)  Problem 1001 区间的价值 Accept: 0    Submit: 0 Time Limit: 10000/5000 mSec(Java/Others)    Memory Limit : 65536 KB  Problem Description  Input  Output  Sample Input

第五届“Astar百度之星程序设计大赛”正式向全国高校学生启动

本报讯(记者高天赋 实习生沈梦菲)近日,第五届"Astar百度之星程序设计大赛"正式面向全国高校学生启动. "Astar百度之星程序设计大赛"是百度公司从2005年起创办的一项校园赛事,旨在为广大程序设计爱好者搭建一个比试身手.切磋交流的平台,大赛创办至今已经吸引了数万名参与者,众多程序设计高手通过大赛脱颖而出. 据介绍,今年的"Astar百度之星程序设计大赛"面向全国所有高校的在校学生,不分年级.专业,均可报名参加,通过在线资格赛.晋级赛等一系

百度之星总冠军乔明达:编程就像玩游戏有趣

在百度之星的历届冠军选手中,乔明达无疑是一个让人大跌眼镜的存在.2013年,这个来自南京外国语学校的17岁少年将冠军宝座收入囊中,赢得了现场一片不可思议的惊叹.在以往的接触中,乔明达给我们留下的印象是一个面对镜头局促羞涩,私下却总是笑容满面,亲切的如同邻家弟弟的大男孩. 正是这个大男孩,在国内外各项赛事中都取得过令人瞩目的成绩:第5届亚洲与太平洋地区信息学http://www.aliyun.com/zixun/aggregation/34147.html">奥林匹克竞赛国际金牌(2011年

百度之星Astar2009程序设计大赛落幕

7月23日消息,由百度举办的"百度之星Astar2009程序设计大赛"在京圆满落幕.来自复旦大学的冯国栋表现出色,从两万多名参赛的程序设计高手中脱颖而出,最终捧得了"2009年百度之星"桂冠. 自2005年创办以来,"Astar百度之星程序设计大赛"已经成为中国互联网中规模最大.最具影响力的程序开发设计赛事.据主办方百度介绍,今年的大赛历时2个月,参赛选手包括清华.北大.复旦.香港中文大学等1000多所高校,以及全国百强中学的部分高中学生,这也代