简单算法讲解材料.ppt

ACM/ICPC程序设计简单算法计算机学院张淑平模拟算法及题目枚举算法及题目贪心算法及题目综合实例一个简单的模拟题题目(zju1708:RobotMotion) 以矩阵形式给定一张地图和机器人的初始位置。矩阵上每一点的字母代表在这一点机器人的移动方向。如果机器人按图中信息能走出的话输出需要的步数。如果机器人进入某个循环则输出循环前所走的步数和循环的长度。Sampleinputandoutput:SampleInput365NEESWE451SESWEEESNWNWEENEWSEN000SampleOutput10step(s)toexit3step(s)beforealoopof8step(s)运行演示place=1row=0col=4N-1S-2W-3E-4365NEESWEEESWE-4-2-3-4-3-3-3-4-2-2-2-1-3-3-3-3运行演示place=2row=0col=3-1-4-4-2-3-4-3-4-4-2-3-4-2-1-3-3-3-3-1-4-4-21-4-3-3-3-4-2-2-2-1-3-3-3-3运行演示place=3row=1col=3-1-4-4-21-4-3-4-4-2-3-4-2-1-3-3-3-3-1-4-421-4-3-3-3-4-2-2-2-1-3-3-3-3运行演示place=3row=1col=3-1-4-421-4109-334-2-28765-3place=11row=1col=-1满足结束条件:col<0输出:10step(s)toexit同理Grid2结束状态为:1-41110-423498-1-3567-4-3-2-4-1place=12row=1line=2满足结束条件2:data[row][col]>0输出:3step(s)beforealoopof8step(s)data[row][col]-1place-data[row][col]