vkdbpqWML7
HightHit
2019-03-15 16:48

蓝桥杯 测试提示运行错误怎么回事呢

  • c语言

/*问题描述
  学霸抢走了大家的作业,班长为了帮同学们找回作业,决定去找学霸决斗。但学霸为了不要别人打扰,住在一个城堡里,城堡外面是一个二维的格子迷宫,要进城堡必须得先通过迷宫。因为班长还有妹子要陪,磨刀不误砍柴功,他为了节约时间,从线人那里搞到了迷宫的地图,准备提前计算最短的路线。可是他现在正向妹子解释这件事情,于是就委托你帮他找一条最短的路线。
输入格式
  第一行两个整数n, m,为迷宫的长宽。
  接下来n行,每行m个数,数之间没有间隔,为0或1中的一个。0表示这个格子可以通过,1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方,即左上角,迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里,每次移动算一步。数据保证(1,1),(n,m)可以通过。
输出格式
  第一行一个数为需要的最少步数K。
  第二行K个字符,每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径,选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110

Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD

Output Sample 2:
4
DDRR
数据规模和约定
  有20%的数据满足:1<=n,m<=10
  有50%的数据满足:1<=n,m<=50
  有100%的数据满足:1<=n,m<=500。
*/

#include
#include
#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4
//起点 终点
int route(int n,int m,char (*map)[501]);
void result(int n,int m,int position ,char (*map)[501]);
char picture[501][501];
char picture_mark[501][501]={0};
int process_record[2][250001]={0};
char stack[250001];
int main(){
int n,m,i,position;
scanf("%d",&n);
scanf("%d",&m);
for(i=0;i<n;i++){
scanf("%s",picture[i]);
}
position=route(n,m,picture);
result(n,m,position,picture);
return 0;

}
int route(int n,int m,char (*map)[501])
{
int i,j,k,x,y;
int position_x,position_y; //搜索顺序 URLD
int last_x,last_y;
int where_p=0,where_q=0,transition=0,transition_record=0;
process_record[0][0]=0;
process_record[1][0]=0;
picture_mark[0][0]=-1; //初始化标记
while(1){

        x=process_record[0][where_p];
        y=process_record[1][where_p];
        //  printf("12 %d %d\n",where_p,where_q);
    if(x==(n-1)&&y==(m-1)){break;}
    if(map[x-1][y]=='0'&picture_mark[x-1][y]==0&&(x-1)>=0){
        where_q++;
        process_record[0][where_q]=x-1;
        process_record[1][where_q]=y;
        picture_mark[x][y+1]=-1;
    }

    if(map[x][y+1]=='0'&&picture_mark[x][y+1]==0&&(y+1)<m){
         where_q++;
        process_record[0][where_q]=x;
        process_record[1][where_q]=y+1;
        picture_mark[x][y+1]=-1;

    }
     if(map[x][y-1]=='0'&&picture_mark[x][y-1]==0&&(y-1)>=0){
        where_q++;
        process_record[0][where_q]=x;
        process_record[1][where_q]=y-1;
        picture_mark[x][y-1]=-1;
    }
       if(map[x+1][y]=='0'&&picture_mark[x+1][y]==0&&(x+1)<n){       //字符0
        where_q++;
        process_record[0][where_q]=x+1;
        process_record[1][where_q]=y;
        picture_mark[x+1][y]=-1;            //遍历标记
    }
        where_p++;

}
    return where_p;

}
//逆向搜索结果
void result(int n,int m,int position ,char (*map)[501]){
int i,j;
int difference_x,difference_y;
int start=0,position_q,position_num;
position_num=position;
position_q=position-1;
while(1){
difference_x=process_record[0][position]-process_record[0][position_q];
difference_y=process_record[1][position]-process_record[1][position_q];

    if(difference_x==-1&&difference_y==0){                 //反着来相邻的只会有一个
            stack[start]='U';
            start++;
            position=position_q;
    }
    else if(difference_x==0&&difference_y==-1){
              stack[start]='L';
              start++;
             position=position_q;
    }
    else if(difference_x==0&&difference_y==1){
             stack[start]='R';
             start++;
             position=position_q;
    }
    else if(difference_x==1&&difference_y==0){
            stack[start]='D';
            start++;
            position=position_q;
    }
        if(position==0){break;}
        position_q--;
    }
    //输出
    start--;
    printf("%d\n",start+1);
    for(i=start;i>=0;i--){
        printf("%c",stack[i]);
    }

    return ;

}


  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

0条回答

为你推荐