兰顿蚂蚁
题目描述
算法设计
关键词：模拟
输入处理
- 地图存入n行m列的数组A[n][m];
- 坐标存入point[2];
- 方向dir;
- 步数step;
代码如下：
//输入处理
int m, n;//m行n列
scanf("%d%d", &m, &n);
int map[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &map[i][j]);
}
}
int point[2];
scanf("%d%d", &point[0], &point[1]);
char dir;
scanf("%c", &dir);
int step;
scanf("%d", &step);
实操时发现创建一个变量currDir表示当前方向，*dir表示所有方向会更方便
修改为：
char curDir;
char dir[4] = {'U', 'R', 'D', 'L'};
scanf("%c", &carDir);
这样就可以通过dir下标的加减实现方向的改变了
但这时又出现了新的问题：
当curDir=‘L’时，若刚好为=需要右转（即下标+1）则会出现数组下标越界的情况。
所以我们可以设置两个“缓冲量”：
char dir[6] = {'L','U', 'R', 'D', 'L','U'};
循环调用时下标从1到4即可。
故：
- 对于“模拟”类型的问题设置一个“当前量”可以方便问题求解
- 数组下标越界可以通过设置“缓冲量”来解决
算法逻辑
核心：模拟蚂蚁的行为
- 根据蚂蚁所在格子类型改变方向和格子类型：
char changeDir(const int *point, int **map, char curDir, const char *dir) {
int type = map[point[0]][point[1]];
//转向
for (int i = 1; i < 5; ++i) {
if (curDir == dir[i] && type) {
curDir = dir[i + 1];
break;
} else if (curDir == dir[i] && !type) {
curDir=dir[i-1];
}
}
map[point[0]][point[1]]=!type;
return curDir;
}
根据方向改变坐标：
void changePoint(int *point, char curDir) { switch (curDir) { case 'U': point[1]+=1; break; case 'R': point[0]+=1; break; case 'D': point[1]-=1; break; case 'L': point[0]-=1; break; default: { } } }循环调用函数且step++：
int curStep=0; do{ changeDir(point, (int **) map, curDir, dir); curStep++; } while (curStep!=step); }这里使用了当型循环，用for也一样。
输出处理
printf("%d %d",point[0],point[1]);
测试运行
。。。。
司空见惯了，找问题吧
原来是忘记调用changeDir函数了，立即修改：
int curStep = 0;
do {
changePoint(point, curDir);
curDir = changeDir(point, (int **) map, curDir, dir);
curStep++;
} while (curStep != step);
再次测试~
呃。。。。
继续找吧，小事。
在适当位置增加输出语句进行调试：
输入测试：
for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { printf("%d ",map[i][j]); } printf("\n"); } printf("%d %d %c %d",point[0],point[1],curDir,step);结果：
立马找到了问题所在：
- curDir扫描失败：缓冲区里的空格赋值给了curDir，这是个老问题了。
scanf("%c", &curDir);解决：**%c前加空格忽略缓冲区中的空白字符**
scanf(" %c", &curDir);- step扫描失败：遇到了‘L’这个非法字符导致扫描停止。
修改后再次运行：
输入没问题了，但结果还是有问题
下面测试changeDir函数
char changeDir(const int *point, int **map, char curDir, const char *dir) {
int type = map[point[0]][point[1]];
printf("type=%d ",type);
//转向
for (int i = 1; i < 5; ++i) {
if (curDir == dir[i] && type) {
curDir = dir[i + 1];
break;
} else if (curDir == dir[i] && !type) {
curDir = dir[i - 1];
}
}
map[point[0]][point[1]] = !type;
printf("curDir=%c ",curDir);
return curDir;
}
运行发现没有输出，说明没有调用该函数，而changePoint应该不会出问题，那么问题很可能 出在二维数组map的调用上。
新增一个列指针p，通过列指针p来实现二维数组map的调用
定义及初始化：
int *p;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &map[i][j]);
}
}
p = map[0];
char changeDir(const int *point, int *p, int n, char curDir, const char *dir) {
int type = *(p + point[0] * n + point[1]);
printf("type=%d ", type);
//转向
for (int i = 1; i < 5; ++i) {
if (curDir == dir[i] && type) {
curDir = dir[i + 1];
break;
} else if (curDir == dir[i] && !type) {
curDir = dir[i - 1];
}
}
*(p + point[0] * n + point[1]) = !type;
printf("curDir=%c ", curDir);
return curDir;
}
运行发现终于出结果了：
仔细一看怎么不对，答案是1，3
那应该是移动也就是changePoint出了问题
果然，题目中point[0]、point[1]分别表示行和列，而在函数中我因为习惯将其当成了坐标进行计算
void changePoint(int *point, char curDir) {
switch (curDir) {
case 'U':
point[1] += 1;
break;
case 'R':
point[0] += 1;
break;
case 'D':
point[1] -= 1;
break;
case 'L':
point[0] -= 1;
break;
default: {
}
}
}
修改后：
void changePoint(int *point, char curDir) {
switch (curDir) {
case 'U':
point[0] -= 1;
break;
case 'R':
point[1] += 1;
break;
case 'D':
point[0] += 1;
break;
case 'L':
point[1] -= 1;
break;
default: {
}
}
}
再次运行：
得到了正确的结果
开开心心提交：
。。。
对了但没完全对，还有一些情况没考虑。
首先，发现在changrDir里少了个brake；
for (int i = 1; i < 5; ++i) {
if (curDir == dir[i] && type) {
curDir = dir[i + 1];
break;
} else if (curDir == dir[i] && type==0) {
curDir = dir[i - 1];
}
}
改为
for (int i = 1; i < 5; ++i) {
if (curDir == dir[i] && type) {
curDir = dir[i + 1];
break;
} else if (curDir == dir[i] && type==0) {
curDir = dir[i - 1];
break;
}
}
运行发现样例结果错了，说明之前的样例通过是个巧合。
然后主方法用do-while会导致计数困难，还是使用fori
for (int i = 0; i < step; ++i) {
changePoint(point,curDir);
curDir= changeDir(point,p,n,curDir,dir);
}
运行：
在changDir处加入输出语句，输出point坐标和该位置改变后的值
找到问题是应该先调用changeDir函数。犯这个错误的原因是一开始以为需要先走后改变方向。
for (int i = 0; i < step; ++i) {
changePoint(point,curDir);
curDir= changeDir(point,p,n,curDir,dir);
}
修改后：
for (int i = 0; i < step; ++i) {
curDir= changeDir(point,p,n,curDir,dir);
changePoint(point,curDir);
}
样例输出正常，再次提交：
终于迎来了胜利！
总结
- 模拟类题目需定义一套“当前量”来表示模拟对象当前的状态
- 数组下标可能越界时可设置几个缓冲量
- 思考二维数组还是以“i行j列”的形式进行
- 当二维数组行和列长度为变量时，想要作为实参传递需要定义列指针*p，*p=a[0];,将*p和列长n作为实参传入函数
