鱼C论坛

 找回密码
 立即注册
查看: 574|回复: 3

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

[复制链接]
发表于 2023-7-7 17:03:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目链接: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..


我的代码
#include <stdio.h>
#include <string.h>
char map[64][64];
int r,c,n;
char action[1024];
int alen;
int startx,starty;
char result[64][64];

int actx[256]; //根据动作字符直接返回x移动量
int acty[256]; //根据动作字符直接返回y移动量


void f(int nowx,int nowy,int actidx){
        if(actidx==alen){
                result[nowx][nowy]='*'; //动作执行完成,保存最终位置 
        }else{
                int nextx=nowx;
                int nexty=nowy;
                while(1){ //只要没撞墙或出界就会一直移动 
                        nextx+=actx[action[actidx]];
                        nexty+=acty[action[actidx]];
                        if(map[nextx][nexty]=='X'||map[nextx][nexty]=='\0') break; //撞墙或出界,停止移动 
                        else{
                                f(nextx,nexty,actidx+1); //在新的位置执行下一个动作 
                        }
                }
        }

}

int main(){
        actx['N']=-1; //初始化动作对应的移动量
        acty['N']=0;
        actx['S']=1;
        acty['S']=0;
        actx['W']=0;
        acty['W']=-1;
        actx['E']=0;
        acty['E']=1;
        while(~scanf("%d%d",&r,&c)){
                memset(map,'\0',sizeof(map));
                memset(action,'\0',sizeof(action));
                for(int i=1;i<=r;i++){
                        for(int j=1;j<=c;j++){
                                char tmp=getchar();
                                while(tmp=='\n') tmp=getchar();
                                map[i][j]=tmp;
                                result[i][j]=tmp;
                                if(tmp=='*'){ //起始位置
                                        startx=i;
                                        starty=j;
                                }
                        }
                }
                map[startx][starty]='.';
                result[startx][starty]='.';
                
                scanf("%d",&n);
                alen=0; //动作序列长度 
                for(int i=0;i<n;i++){
                        char tmp[16];
                        scanf("%s",tmp);
                        if(strcmp(tmp,"NORTH")==0) action[alen++]='N'; //根据输入生成动作序列 
                        else if(strcmp(tmp,"SOUTH")==0) action[alen++]='S';
                        else if(strcmp(tmp,"WEST")==0) action[alen++]='W';
                        else if(strcmp(tmp,"EAST")==0)action[alen++]='E';
                }
                f(startx,starty,0); //从起始点,动作0开始DFS 
                for(int i=1;i<=r;i++){
                        printf("%s\n",result[i]+1);
                }
        }
        
        return 0;
}
最佳答案
2023-7-7 17:05:46
从题目描述来看,你需要在一张小镇的地图上找到小车可能的最终位置。地图上的符号用来表示哪里可以行车,哪里不行。你的代码主要使用了深度优先搜索(DFS)来解决这个问题。

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

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

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

   if (actidx == alen) {       if (1 <= nowx && nowx <= r && 1 <= nowy && nowy <= c) {           result[nowx][nowy] = '*'; // 动作执行完成,保存最终位置       }   }   
3. 当你在 main 函数中读取地图时,你没有考虑到可能会有空白符(例如空格和换行符)作为输入。你应该在读取地图的每个字符时,检查是否为有效字符( . 、 X 或 * ),如果不是,继续读取下一个字符。你可以使用如下循环来读取地图:

   for (int i = 1; i <= r; i++) {       for (int j = 1; j <= c; j++) {           char tmp = getchar();           while (tmp != '.' && tmp != 'X' && tmp != '*') {               tmp = getchar();           }           map[i][j] = tmp;           result[i][j] = tmp;           if (tmp == '*') { // 起始位置               startx = i;               starty = j;           }       }   }   
请尝试修复这些问题,并重新测试你的代码。如果你仍然遇到问题,请随时告诉我,我会尽力帮助你。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-7-7 17:05:46 | 显示全部楼层    本楼为最佳答案   
从题目描述来看,你需要在一张小镇的地图上找到小车可能的最终位置。地图上的符号用来表示哪里可以行车,哪里不行。你的代码主要使用了深度优先搜索(DFS)来解决这个问题。

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

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

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

   if (actidx == alen) {       if (1 <= nowx && nowx <= r && 1 <= nowy && nowy <= c) {           result[nowx][nowy] = '*'; // 动作执行完成,保存最终位置       }   }   
3. 当你在 main 函数中读取地图时,你没有考虑到可能会有空白符(例如空格和换行符)作为输入。你应该在读取地图的每个字符时,检查是否为有效字符( . 、 X 或 * ),如果不是,继续读取下一个字符。你可以使用如下循环来读取地图:

   for (int i = 1; i <= r; i++) {       for (int j = 1; j <= c; j++) {           char tmp = getchar();           while (tmp != '.' && tmp != 'X' && tmp != '*') {               tmp = getchar();           }           map[i][j] = tmp;           result[i][j] = tmp;           if (tmp == '*') { // 起始位置               startx = i;               starty = j;           }       }   }   
请尝试修复这些问题,并重新测试你的代码。如果你仍然遇到问题,请随时告诉我,我会尽力帮助你。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

具体到代码层面,可以通过修改你的递归函数 "f" 来解决这个问题。在每个可移动的地点,我们都可以选择停下,或者继续向前。所以,我们需要在 "f" 函数中增加一个条件来处理汽车在当前地点停下的情况,然后执行下一个动作。具体如下:
void f(int nowx,int nowy,int actidx){
        if(actidx==alen){
                result[nowx][nowy]='*'; //动作执行完成,保存最终位置
        }else{
                int nextx=nowx;
                int nexty=nowy;
                while(1){ //只要没撞墙或出界就会一直移动
                        nextx+=actx[action[actidx]];
                        nexty+=acty[action[actidx]];
                        if(map[nextx][nexty]=='X'||map[nextx][nexty]=='\0') break; //撞墙或出界,停止移动
                        else{
                                f(nextx,nexty,actidx+1); //在新的位置执行下一个动作
                        }
                }
                f(nowx,nowy,actidx+1); //在当前位置停下,执行下一个动作
        }

}

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

希望这个建议对你有所帮助!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-7-7 17:35:48 | 显示全部楼层
谢谢各位大佬了,虽然大佬们的回答很像chatgpt没读懂题一本正经的胡言乱语但确实提供了一些思路,我找到的解决方法为
while(tmp=='\n') tmp=getchar();
修改为:
while(tmp != '.' && tmp != 'X' && tmp != '*') tmp=getchar();

DFS方法修改为BFS方法

打印结果时:
printf("%s\n",map[i]+1);
修改为:
printf("%s\r\n",map[i]+1);
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 08:45

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表