[已解决]这道题我的代码AC不了，但是我实在是找不到问题在哪儿，求助

李杰伟

题目链接：https://acm.swust.edu.cn/#/problem/392/

题目描述
年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车，但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。 那个装置太旧了，以至于只能发射关于那辆车的移动路线的方向信息。 编写程序，通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。 小镇的地图是矩形的，上面的符号用来标明哪儿可以行车哪儿不行。“.”表示小镇上那块地方是可以行车的，而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示，且汽车能从初始位置通过。 汽车能向四个方向移动：向北(向上)，向南(向下)，向西(向左)，向东(向右)。 拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向，拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

输入
输入文件的第一行包含两个用空格隔开的自然数R和C，1≤R≤50，1≤C≤50，分别表示小镇地图中的行数和列数。
以下的R行中每行都包含一组C个符号(“.”或“X”或“*”)用来描述地图上相应的部位。
接下来的第R+2行包含一个自然数N，1≤N≤1000，表示一组方向的长度。
接下来的N行幅行包含下述单词中的任一个：NORTH(北)、SOUTH(南)、WEST(西)和EAST(东)，表示汽车移动的方向，任何两个连续的方向都不相同。
输出
输出文件应包含用R行表示的小镇的地图(象输入文件中一样)，字符“*”应该仅用来表示汽车最终可能出现的位置。

样例输入
4 5
.....
.X...
...*X
X.X..
3
NORTH
WEST
SOUTH

样例输出
.....
*X*..
*.*.X
X.X..


我的代码

1. #include <stdio.h>
   
2. #include <string.h>
   
3. char map[64][64];
   
4. int r,c,n;
   
5. char action[1024];
   
6. int alen;
   
7. int startx,starty;
   
8. char result[64][64];
   
9. 
   
10. int actx[256]; //根据动作字符直接返回x移动量
    
11. int acty[256]; //根据动作字符直接返回y移动量
    
12. 
    
13. 
    
14. void f(int nowx,int nowy,int actidx){
    
15.         if(actidx==alen){
    
16.                 result[nowx][nowy]='*'; //动作执行完成，保存最终位置
    
17.         }else{
    
18.                 int nextx=nowx;
    
19.                 int nexty=nowy;
    
20.                 while(1){ //只要没撞墙或出界就会一直移动
    
21.                         nextx+=actx[action[actidx]];
    
22.                         nexty+=acty[action[actidx]];
    
23.                         if(map[nextx][nexty]=='X'||map[nextx][nexty]=='\0') break; //撞墙或出界，停止移动
    
24.                         else{
    
25.                                 f(nextx,nexty,actidx+1); //在新的位置执行下一个动作
    
26.                         }
    
27.                 }
    
28.         }
    
29. 
    
30. }
    
31. 
    
32. int main(){
    
33.         actx['N']=-1; //初始化动作对应的移动量
    
34.         acty['N']=0;
    
35.         actx['S']=1;
    
36.         acty['S']=0;
    
37.         actx['W']=0;
    
38.         acty['W']=-1;
    
39.         actx['E']=0;
    
40.         acty['E']=1;
    
41.         while(~scanf("%d%d",&r,&c)){
    
42.                 memset(map,'\0',sizeof(map));
    
43.                 memset(action,'\0',sizeof(action));
    
44.                 for(int i=1;i<=r;i++){
    
45.                         for(int j=1;j<=c;j++){
    
46.                                 char tmp=getchar();
    
47.                                 while(tmp=='\n') tmp=getchar();
    
48.                                 map[i][j]=tmp;
    
49.                                 result[i][j]=tmp;
    
50.                                 if(tmp=='*'){ //起始位置
    
51.                                         startx=i;
    
52.                                         starty=j;
    
53.                                 }
    
54.                         }
    
55.                 }
    
56.                 map[startx][starty]='.';
    
57.                 result[startx][starty]='.';
    
58.                
    
59.                 scanf("%d",&n);
    
60.                 alen=0; //动作序列长度
    
61.                 for(int i=0;i<n;i++){
    
62.                         char tmp[16];
    
63.                         scanf("%s",tmp);
    
64.                         if(strcmp(tmp,"NORTH")==0) action[alen++]='N'; //根据输入生成动作序列
    
65.                         else if(strcmp(tmp,"SOUTH")==0) action[alen++]='S';
    
66.                         else if(strcmp(tmp,"WEST")==0) action[alen++]='W';
    
67.                         else if(strcmp(tmp,"EAST")==0)action[alen++]='E';
    
68.                 }
    
69.                 f(startx,starty,0); //从起始点，动作0开始DFS
    
70.                 for(int i=1;i<=r;i++){
    
71.                         printf("%s\n",result[i]+1);
    
72.                 }
    
73.         }
    
74.        
    
75.         return 0;
    
76. }

复制代码

最佳答案

月排行榜 / 总排行榜

陶远航

2023-7-7 17:05:46

从题目描述来看，你需要在一张小镇的地图上找到小车可能的最终位置。地图上的符号用来表示哪里可以行车，哪里不行。你的代码主要使用了深度优先搜索（DFS）来解决这个问题。

我注意到了一些你的代码中可能导致错误的地方：

1. 当你在处理输入时，你并没有清除 result 数组。这可能导致在连续测试用例之间有残留数据。你可以在每次开始处理新的输入之前，使用 memset(result, '\0', sizeof(result)); 来清除 result 数组。

2. 在 f 函数中，当你执行完所有动作后，你应该检查当前位置是否在地图范围内（1<=x<=r 和 1<=y<=c）。如果不在范围内，你不应该把 * 放在 result 数组中。你可以添加如下检查：

  

1.    if (actidx == alen) {
2.        if (1 <= nowx && nowx <= r && 1 <= nowy && nowy <= c) {
3.            result[nowx][nowy] = '*'; // 动作执行完成，保存最终位置
4.        }
5.    }
6.    

复制代码

3. 当你在 main 函数中读取地图时，你没有考虑到可能会有空白符（例如空格和换行符）作为输入。你应该在读取地图的每个字符时，检查是否为有效字符（ . 、 X 或 * ），如果不是，继续读取下一个字符。你可以使用如下循环来读取地图：

  

1.    for (int i = 1; i <= r; i++) {
2.        for (int j = 1; j <= c; j++) {
3.            char tmp = getchar();
4.            while (tmp != '.' && tmp != 'X' && tmp != '*') {
5.                tmp = getchar();
6.            }
7.            map[i][j] = tmp;
8.            result[i][j] = tmp;
9.            if (tmp == '*') { // 起始位置
10.                startx = i;
11.                starty = j;
12.            }
13.        }
14.    }
15.    

复制代码

请尝试修复这些问题，并重新测试你的代码。如果你仍然遇到问题，请随时告诉我，我会尽力帮助你。

跳转到最佳答案楼层

陶远航

从题目描述来看，你需要在一张小镇的地图上找到小车可能的最终位置。地图上的符号用来表示哪里可以行车，哪里不行。你的代码主要使用了深度优先搜索（DFS）来解决这个问题。

我注意到了一些你的代码中可能导致错误的地方：

1. 当你在处理输入时，你并没有清除 result 数组。这可能导致在连续测试用例之间有残留数据。你可以在每次开始处理新的输入之前，使用 memset(result, '\0', sizeof(result)); 来清除 result 数组。

2. 在 f 函数中，当你执行完所有动作后，你应该检查当前位置是否在地图范围内（1<=x<=r 和 1<=y<=c）。如果不在范围内，你不应该把 * 放在 result 数组中。你可以添加如下检查：

  

1.    if (actidx == alen) {
2.        if (1 <= nowx && nowx <= r && 1 <= nowy && nowy <= c) {
3.            result[nowx][nowy] = '*'; // 动作执行完成，保存最终位置
4.        }
5.    }
6.    

复制代码

3. 当你在 main 函数中读取地图时，你没有考虑到可能会有空白符（例如空格和换行符）作为输入。你应该在读取地图的每个字符时，检查是否为有效字符（ . 、 X 或 * ），如果不是，继续读取下一个字符。你可以使用如下循环来读取地图：

  

1.    for (int i = 1; i <= r; i++) {
2.        for (int j = 1; j <= c; j++) {
3.            char tmp = getchar();
4.            while (tmp != '.' && tmp != 'X' && tmp != '*') {
5.                tmp = getchar();
6.            }
7.            map[i][j] = tmp;
8.            result[i][j] = tmp;
9.            if (tmp == '*') { // 起始位置
10.                startx = i;
11.                starty = j;
12.            }
13.        }
14.    }
15.    

复制代码

请尝试修复这些问题，并重新测试你的代码。如果你仍然遇到问题，请随时告诉我，我会尽力帮助你。

isdkz

首先，根据你的问题描述，这个问题的关键在于处理移动路径的所有可能性。当汽车移动时，如果遇到多个可移动的地点，那么汽车可能停在这些地点的任意一个。在你的代码中，你的递归函数 "f" 的设计逻辑是：如果没撞墙或出界就会一直移动，然后在每一个可以移动的地点执行下一个动作。这个设计忽略了汽车可以在任意可移动地点停下的情况，只考虑了汽车会一直移动到不能移动为止。这是代码的主要问题。

具体到代码层面，可以通过修改你的递归函数 "f" 来解决这个问题。在每个可移动的地点，我们都可以选择停下，或者继续向前。所以，我们需要在 "f" 函数中增加一个条件来处理汽车在当前地点停下的情况，然后执行下一个动作。具体如下：

1. void f(int nowx,int nowy,int actidx){
   
2.         if(actidx==alen){
   
3.                 result[nowx][nowy]='*'; //动作执行完成，保存最终位置
   
4.         }else{
   
5.                 int nextx=nowx;
   
6.                 int nexty=nowy;
   
7.                 while(1){ //只要没撞墙或出界就会一直移动
   
8.                         nextx+=actx[action[actidx]];
   
9.                         nexty+=acty[action[actidx]];
   
10.                         if(map[nextx][nexty]=='X'||map[nextx][nexty]=='\0') break; //撞墙或出界，停止移动
    
11.                         else{
    
12.                                 f(nextx,nexty,actidx+1); //在新的位置执行下一个动作
    
13.                         }
    
14.                 }
    
15.                 f(nowx,nowy,actidx+1); //在当前位置停下，执行下一个动作
    
16.         }
    
17. 
    
18. }
    

复制代码

然后为了避免无效的递归调用，我们还需要记录汽车已经访问过的位置。这样，在递归调用 "f" 函数时，我们只需要考虑那些尚未访问过的位置。为此，我们需要在你的代码中增加一个二维数组 "visited"，用来记录每个位置是否已经被访问过。

希望这个建议对你有所帮助！

李杰伟

谢谢各位大佬了，虽然大佬们的回答很像chatgpt没读懂题一本正经的胡言乱语但确实提供了一些思路，我找到的解决方法为

1. while(tmp=='\n') tmp=getchar();
   
2. 修改为：
   
3. while(tmp != '.' && tmp != 'X' && tmp != '*') tmp=getchar();
   
4. 
   
5. DFS方法修改为BFS方法
   
6. 
   
7. 打印结果时：
   
8. printf("%s\n",map[i]+1);
   
9. 修改为：
   
10. printf("%s\r\n",map[i]+1);

复制代码