4-简单算法.ppt

ACM/ICPC程序设计 简单算法 模拟算法及题目 枚举算法及题目 贪心算法及题目 综合实例 一个简单的模拟题 题目（zju1708：Robot Motion） 以矩阵形式给定一张地图和机器人的初始位置。矩阵上每一点的字母代表在这一点机器人的移动方向。如果机器人按图中信息能走出的话输出需要的步数。如果机器人进入某个循环则输出循环前所走的步数和循环的长度。 Sample input and output： Sample Input 3 6 5NEESWEWWWESSSNWWWW4 5 1SESWEEESNWNWEENEWSEN0 0 0 Sample Output 10 step(s) to exit3 step(s) before a loop of 8 step(s) 问题分析 我们有什么信息？ 地图，起点 我们要什么？ 移动结束（走出边界或遇到以前走过的点）时，该次移动的序号。（如果是遇到以前走过的点，还需知道该点的序号） 设计数据结构 主要信息： int data[100][100]; //存放地图 int place; //当前序号 int m,n; //矩阵大小 int begin; //起始位置 方法： 按照地图及初态移动机器人直到满足结束条件：下一个要经过的点（row，line）满足（row0 || row=m || line 0 || line= n) 或 data[row][line] 0.用place ++标记刚走过的点。 如果走出地图输出：place －1 step(s) to exit 。 否则输出：data[row][line]-1 step(s) before a loop of place-data[row] [line] step(s) 运行演示 运行演示 同理Grid2结束状态为： Robot Motion 程序 #include iostream using namespace std; int data[100][100]; // 地图 int place; // 当前位置 int m,n,begin; // 地图大小，初始位置 void move(int row,int col)；//按要求移动机器人 int main(){ return 0; } Robot Motion 程序(续) int main(){ char ch; while( (cinmnbegin) m){ //输入数据 place=1; for(int i=0;im;i++) for(int j=0;jn;j++){ cinch; switch (ch){ //把字符转换成整数以便于统一处理 case N: data[i][j]=-1; break; case S: data[i][j]=-2; break; case W: data[i][j]=-3; break; case E: data[i][j]=-4; break; } } move(0,begin-1); } //end of while return 0; } //end of main Robot Motion 程序(续) void move(int row,int col) { bool notExit=true; while( notExit (data[row][col]0) ) { int d = data[row][col]; data[row][col]= place; switch (d) { case -1: row--; break; case -2: row++; break; case -3: col--; break; case -4: col++; break; } place++; notExit = (row-1)(rowm)(col-1)(coln); } //end of while if(!notExit) coutplace-1 step(s) to exitendl; else coutdata[row][line]-1 step(s) before a loop of place-data[row][line] step(s)endl; } //end of move 结论：一个简洁高效的算法在很大程度上依赖于数据结构的建立。这也往