POJ-1573的解题思路是什么？
- 内容介绍
- 文章标签
- 相关推荐
本文共计576个文字，预计阅读时间需要3分钟。
原创新品，引领潮流。探索未知，激发创意。简约设计，极致体验。
#include <stdio.h>
#include <malloc.h>
struct gridCell{
char direction;
bool passed;
int step;
};
typedef struct gridCell gridCell;
typedef struct moveRecord moveRecord;
void moveRobot(gridCell **grid, int beginColumn, int gridLength, int gridWidth) {
int curY = 0;
int curX = beginColumn - 1;
int steps = 0;
while(1) {
if (curY < 0 || curX <0 || curX >= gridLength || curY >= gridWidth) {
printf("%d step(s) to exit\n", steps);
break;
}
if (grid[curY][curX].passed == true) {
printf("%d step(s) before a loop of %d step(s)\n", grid[curY][curX].step - 1, steps - grid[curY][curX].step + 1);
break;
}
grid[curY][curX].passed = true;
grid[curY][curX].step = ++steps;
switch (grid[curY][curX].direction) {
case 'N':
curY--;
break;
case 'E':
curX++;
break;
case 'S':
curY++;
break;
case 'W':
curX--;
break;
}
}
}
int main() {
while(1) {
int length, width, beginColumn;
char tmp;
scanf("%d %d %d", &width, &length, &beginColumn);
scanf("%c", &tmp);
if (length == 0 && width == 0 && beginColumn == 0) {
return 0;
}
gridCell **grid = (gridCell **) malloc(width * sizeof(gridCell *));
for (int i = 0; i < width; i++) {
grid[i] = (gridCell *)malloc(length * sizeof(gridCell));
}
for (int i = 0; i < width; i++) {
for (int j = 0; j < length; j++) {
scanf("%c", &(grid[i][j].direction));
// printf("===%c=== %d %d \n", grid[i][j].direction, i, j);
grid[i][j].passed = false;
grid[i][j].step = -1;
}
scanf("%c", &tmp);
}
moveRobot(grid, beginColumn, length, width);
// for (int i = 0; i < width; i++) {
// for (int j = 0; j < length; j++) {
// printf("%c ", grid[i][j].direction);
// }
// printf("\n");
// }
for (int i = 0; i < width; i++) {
free(grid[i]);
grid[i] = NULL;
}
free(grid);
grid = NULL;
}
}
还是纯模拟， 没啥很强的技巧或者算法， 只是繁琐。
有几个点:
1. 在接受输入时， 因为字母是挨着的， 所以用%c, 那么要注意在每次输完一行的时候， 加一个 scanf("%c", &tmp); 把'\n'给吃掉。
2. 在本题能感受到一种合适的数据封装和抽象能方便问题， 在grid的每一格， 除了记录方向和是否经过外，也记下了这是第几步经过的， 这样在后面求loop
很方便， 最一开始没想到， 还想搞一个专门的轨迹数组。。。。。 以后要注意培养这方面的能力， 数据的合理记录和封装.
3. 因为输入时， grid的最上一行其实在输入时变成了数组的最下行， 那么就把 'S' 和 ‘N’的前进方向互换就可以直接用生成的上下颠倒的数组了.
本文共计576个文字，预计阅读时间需要3分钟。
原创新品，引领潮流。探索未知，激发创意。简约设计，极致体验。
#include <stdio.h>
#include <malloc.h>
struct gridCell{
char direction;
bool passed;
int step;
};
typedef struct gridCell gridCell;
typedef struct moveRecord moveRecord;
void moveRobot(gridCell **grid, int beginColumn, int gridLength, int gridWidth) {
int curY = 0;
int curX = beginColumn - 1;
int steps = 0;
while(1) {
if (curY < 0 || curX <0 || curX >= gridLength || curY >= gridWidth) {
printf("%d step(s) to exit\n", steps);
break;
}
if (grid[curY][curX].passed == true) {
printf("%d step(s) before a loop of %d step(s)\n", grid[curY][curX].step - 1, steps - grid[curY][curX].step + 1);
break;
}
grid[curY][curX].passed = true;
grid[curY][curX].step = ++steps;
switch (grid[curY][curX].direction) {
case 'N':
curY--;
break;
case 'E':
curX++;
break;
case 'S':
curY++;
break;
case 'W':
curX--;
break;
}
}
}
int main() {
while(1) {
int length, width, beginColumn;
char tmp;
scanf("%d %d %d", &width, &length, &beginColumn);
scanf("%c", &tmp);
if (length == 0 && width == 0 && beginColumn == 0) {
return 0;
}
gridCell **grid = (gridCell **) malloc(width * sizeof(gridCell *));
for (int i = 0; i < width; i++) {
grid[i] = (gridCell *)malloc(length * sizeof(gridCell));
}
for (int i = 0; i < width; i++) {
for (int j = 0; j < length; j++) {
scanf("%c", &(grid[i][j].direction));
// printf("===%c=== %d %d \n", grid[i][j].direction, i, j);
grid[i][j].passed = false;
grid[i][j].step = -1;
}
scanf("%c", &tmp);
}
moveRobot(grid, beginColumn, length, width);
// for (int i = 0; i < width; i++) {
// for (int j = 0; j < length; j++) {
// printf("%c ", grid[i][j].direction);
// }
// printf("\n");
// }
for (int i = 0; i < width; i++) {
free(grid[i]);
grid[i] = NULL;
}
free(grid);
grid = NULL;
}
}
还是纯模拟， 没啥很强的技巧或者算法， 只是繁琐。
有几个点:
1. 在接受输入时， 因为字母是挨着的， 所以用%c, 那么要注意在每次输完一行的时候， 加一个 scanf("%c", &tmp); 把'\n'给吃掉。
2. 在本题能感受到一种合适的数据封装和抽象能方便问题， 在grid的每一格， 除了记录方向和是否经过外，也记下了这是第几步经过的， 这样在后面求loop
很方便， 最一开始没想到， 还想搞一个专门的轨迹数组。。。。。 以后要注意培养这方面的能力， 数据的合理记录和封装.
3. 因为输入时， grid的最上一行其实在输入时变成了数组的最下行， 那么就把 'S' 和 ‘N’的前进方向互换就可以直接用生成的上下颠倒的数组了.