1.5s时间超限 深度优先搜索 c语言

解题思路:

通过深度优先搜索，找到以初始字符为开头的最长数字（字符串），通过比较最长数字与当前数字得出最终结果

注意事项:

时间超限

记得每次退格的时候把当前数字的最后一位去掉

参考代码:

#include <stdio.h>

#include <string.h>

char square[25][15][15];//初始数组

char resl[25][31];//结果数字

void finding(int n, int hight, int wide){

    char lock[hight][wide];//工作数组

    char now[30];//当前数字

    memset(resl[n], '\0', 31);

    int cnth = 0, cntw = 0, number = 0, con, conw = 0, les = 0, place[31];//place变量用来记录当前步向哪个方向移动

    memset(place, 0, 30 * sizeof(int));

    memset(now, '\0', 30);

    for(con = 0; con < hight; con++){

        strcpy(lock[con], square[n][con]);   

    }

    for(con = 0; con < hight; con++){

        for(conw = 0; conw < wide; conw++){

            cnth = con;

            cntw = conw;

            now[number] = lock[cnth][cntw];

            if(now[number] == '#'){

                number = 0;

            }else{

                while(1){

                    lock[cnth][cntw] = '#';//把走过的位置变为‘#’锁住

                    if(cnth != 0 && lock[cnth - 1][cntw] != '#' && place[number + 1] < 5){//最后一个判断防止退格后步骤重复

                        cnth -= 1;

                        place[number + 1] = 1;

                    }else if(cntw != 0 && lock[cnth][cntw - 1] != '#' && place[number + 1] < 6){

                        cntw -= 1;

                        place[number + 1] = 2;

                    }else if(cntw < wide - 1 && lock[cnth][cntw + 1] != '#' && place[number + 1] < 7){

                        cntw += 1;

                        place[number + 1] = 3;

                    }else if(cnth < hight - 1 && lock[cnth + 1][cntw] != '#' && place[number + 1] < 8){

                        cnth += 1;

                        place[number + 1] = 4;

                    }else{

                        if(strlen(now) > strlen(resl[n]) || (strlen(now) == strlen(resl[n]) && strcmp(now, resl[n]) > 0)){//判断长度，如果长度一样就判断大小

                            strcpy(resl[n], now);

                        }else if(number == 0 || number > 29){

                            break;

                        }

                            switch(place[number]){

                                case 1: lock[cnth][cntw] = now[number]; cnth += 1; place[number] = 5; break;//判断退格方向

                                case 2: lock[cnth][cntw] = now[number]; cntw += 1; place[number] = 6; break;

                                case 3: lock[cnth][cntw] = now[number]; cntw -= 1; place[number] = 7; break;

                                case 4: lock[cnth][cntw] = now[number]; cnth -= 1; place[number] = 8; break;

                            }

                            place[number + 1] = 0;

                            now[number] = '\0';//把当前数字最后一位删除

                            number -= 1;

                            continue;//跳过数字记录步骤，直接进行下一轮循环

                    }

                    number += 1;

                    now[number] = lock[cnth][cntw];

                }

                memset(now, '\0', 30);

                number = 0;

                memset(place, 0, 31 * sizeof(int));

                for(cnth = 0; cnth < hight; cnth++){

                    strcpy(lock[cnth], square[n][cnth]);   

                }

            }

        }

    }

}

int main(){

    int hight, wide, cnt;

    int number = 0;

    scanf("%d %d", &hight, &wide);

    while(hight != 0){

        for(cnt = 0; cnt < hight; cnt++){

        memset(square[number][cnt], 0, 15 * sizeof(int));

            scanf("%s", &square[number][cnt]);

        }

        finding(number, hight, wide);

        number += 1;

        scanf("%d %d", &hight, &wide);

    }

    for(cnt = 0; cnt < number; cnt++){

        printf("%s", resl[cnt]);

        printf("\n");

    }

    return 0;

}