华为od统一考试B卷【单词搜索】C语言实现

一时失言乱红尘 2023-09-26 21:31 19阅读 0赞

**所有题目均有五种语言实现。[C实现目录][C]、[C++ 实现目录][C_]、[Python实现目录][Python]、[Java实现目录][Java]、[JavaScript实现目录][JavaScript]**

## 题目 ##

> 找到它是一个小游戏，你需要在一个矩阵中找到给定的单词。
> 
> 假设给定单词 HELLOWORD，在矩阵中只要能找到 H->E->L->L->O->W->O->R->L->D连成的单词，就算通过。
> 
> 注意区分英文字母大小写，并且您只能上下左右行走，不能走回头路。
> 
> **输入描述**
> 
> 输入第 1 行包含两个整数 n、m (0 < n,m < 21) 分别表示 n 行 m 列的矩阵，
> 
> 第 2 行是长度不超过100的单词 W (在整个矩阵中给定单词 W 只会出现一次)，
> 
> 从第 3 行到第 n+2 行是指包含大小写英文字母的长度为 m 的字符串矩阵。
> 
> **输出描述**
> 
> 如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置(第几行 第几列)，
> 
> 否则输出“NO”。
> 
> **示例1** 输入输出示例仅供调试，后台判题数据一般不包含示例
> 
> **输入**
> 
> 5 5
> 
> HELLOWORLD
> 
> CPUCY
> 
> EKLQH
> 
> CHELL
> 
> LROWO
> 
> DGRBC
> 
> **输出**
> 
> 3 2

## 思路 ##

> 1：关于搜索类的题目，不是BFS 就是DFS，套路都是一样的。这一题属于一道比较简单的搜索题。
> 
> 2：注意两个变量，第一个、布尔数组变量visited，判断是否搜索过。第二个、布尔变量判断是否找到。

## C语言输入输出 ##

> 机试的输入数据常要求有多组，并且格式多种多样，这是初次登机试平台的同学的一个障碍。实际上，这些格式可以归为固定的几种类型，这里介绍各种类型的处理方法，以帮助同学们克服这些障碍。
> 
> **1：简单输入**
> 
>     #include <stdio.h>
>     int main()
>     {
>         int a,b;
>         scanf("%d %d",&a, &b);
>         printf("%d\n",a+b);  //对其他题目，换成要求的复杂处理与输出
>         return 0;
>     }
> 
> **2：输入多组数据，直到读至输入文件末尾（EOF）为止**
> 
>     #include <stdio.h>
>     int main() 
>     {
>     	int a,b;
>     	while(scanf("%d %d",&a, &b) != EOF) // 输入结束时，scanf函数返回值为EOF(-1)，即没有数据输入时会退出while循环
>     	{
>     		printf("%d\n",a+b);
>     	}
>     	return 0; 
>     }
> 
> 3：输入多组数据，组数由第一个输入数据决定（在开始的时候输入一个N，接下来是N组数据）
> 
>     #include<stdio.h>
>     int main()
>     {
>     	int n,i;
>     	int a,b;
>     	scanf("%d",&n);
>     	for(i=0;i<n;i++)
>     	{
>     		scanf("%d%d",&a,&b);
>     		printf("%d\n",a+b);
>     	}
>     	return 0;
>     }
> 
> 具体我参考的是这篇文章，各位同学注意一定要把输入输出练熟悉了，有很多同学都是有了思路，遇到一个比较奇怪的输入输出就不知道咋写了，非常可惜。
> 
> 我参考的是这篇文章，讲的还是比较全的：
> 
> [ACM题目中输入数据的处理（C语言版）\_迂者-贺利坚的博客-CSDN博客\_算法中循环输入用例][ACM_C_-_-CSDN]

## Code ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>
    #include <math.h>
    #include <float.h>
     
    #define CEILING_POS(X) ((X-(int)(X)) > 0 ? (int)(X+1) : (int)(X))
    #define CEILING_NEG(X) ((X-(int)(X)) < 0 ? (int)(X-1) : (int)(X))
    #define CEILING(X) ( ((X) > 0) ? CEILING_POS(X) : CEILING_NEG(X) )
     
    #define MIN(a, b) ((a) < (b)) ? (a) : (b)
    #define MAX(a, b) ((a) > (b)) ? (a) : (b)
     
    int cmpfunc (const void * a, const void * b) {
       return ( *(int*)a - *(int*)b );
    }
    //qsort(dp, m+1, sizeof(int), cmpfunc);
    
    bool find(int N, int M, char matrix[][M], bool visited[][M], int x, int y,
              char* s, int k) {
        if (matrix[x][y] != s[k]) {
            return false;
        } else if (k == strlen(s) - 1) {
            return true;
        }
        printf("%d %d\n", x,y);
        visited[x][y] = true;
        int dic[4][2] = {
        {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        bool result = false;
        for (int i = 0; i < 4; ++i) {
            int newx = x + dic[i][0], newy = y + dic[i][1];
            if (newx >= 0 && newx < N && newy >= 0 && newy < M) {
                
                if (!visited[newx][newy]) {
                    printf("%d %d\n", newx,newy);
                    bool found = find(N, M, matrix, visited, newx, newy, s, k + 1);
                    if (found) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[x][y] = false;
        return result;
    } 
     
    int main () {
        int N, M;
        scanf("%d %d", &M, &N);
        char word[1000];
        scanf("%s", word);
        char matrix[N][M];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                scanf("%c", &matrix[i][j]);
            }
        }
        
        bool visited[N][M];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = false;
            }
        }
        find( N,M, matrix, visited, 2, 1, word, 0);
        /*
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; j++) {
                bool found = find( N,M, matrix, visited, i, j, word, 0);
                if (found) {
                    printf("%d %d\n", i + 1, j + 1);
                    return;
                }
            }
        }*/
        printf("NO\n");
    5 5
    HELLOWORLD
    CPUCY
    EKLQH
    CHELL
    LROWO
    DGRBC
    
        return 0;
     
    }

### 要求 ###

> 时间限制：C/C++ 1秒，其他语言 2秒
> 
> 空间限制：C/C++262144K，其他语言524288K
> 
> 64bit IO Format：%lld
> 
> 语言限定：  
> C（clang11）, C++（clang++11）, Pascal（fpc 3.0.2）, Java（javac 1.8）, Python2（2.7.3）,  
> PHP(7.4.7), C\#(mcs5.4), ObjC(gcc 5.4), Pythen3(3.9), JavaScript Node(12.18.2), JavaScript V8(6.0.0),  
> Sqlite(3.7.9), R(4.0.3), Go(1.14.4), Ruby(2.7.1), Swift(5.3), matlab(Octave 5.2), Pypy2(pypy2.7.13),  
> Pypy3(pypy3.6.1), Rust(1.44), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2), Mysql(8.0)

[C]: https://renjie.blog.csdn.net/article/details/129190260
[C_]: https://blog.csdn.net/misayaaaaa/category_12036814.html
[Python]: https://blog.csdn.net/misayaaaaa/category_12111005.html
[Java]: https://blog.csdn.net/misayaaaaa/category_12111006.html
[JavaScript]: https://blog.csdn.net/misayaaaaa/category_12199270.html
[ACM_C_-_-CSDN]: https://blog.csdn.net/sxhelijian/article/details/8978794