devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：凡人多烦事01 | 2024-02-17 03:05:29

赞

踩

华为 od c语言

        所有题目均有五种语言实现。C实现目录、C++ 实现目录、Python实现目录、Java实现目录、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：简单输入

  1. #include <stdio.h>
  2. int main()
  3. {
  4.     int a,b;
  5.     scanf("%d %d",&a, &b);
  6.     printf("%d\n",a+b);  //对其他题目，换成要求的复杂处理与输出
  7.     return 0;
  8. }

2：输入多组数据，直到读至输入文件末尾（EOF）为止

  1. #include <stdio.h>
  2. int main() 
  3. {
  4. 	int a,b;
  5. 	while(scanf("%d %d",&a, &b) != EOF) // 输入结束时，scanf函数返回值为EOF(-1)，即没有数据输入时会退出while循环
  6. 	{
  7. 		printf("%d\n",a+b);
  8. 	}
  9. 	return 0; 
  10. }

  3：输入多组数据，组数由第一个输入数据决定（在开始的时候输入一个N，接下来是N组数据）

  1. #include<stdio.h>
  2. int main()
  3. {
  4. 	int n,i;
  5. 	int a,b;
  6. 	scanf("%d",&n);
  7. 	for(i=0;i<n;i++)
  8. 	{
  9. 		scanf("%d%d",&a,&b);
  10. 		printf("%d\n",a+b);
  11. 	}
  12. 	return 0;
  13. }

        具体我参考的是这篇文章，各位同学注意一定要把输入输出练熟悉了，有很多同学都是有了思路，遇到一个比较奇怪的输入输出就不知道咋写了，非常可惜。

        我参考的是这篇文章，讲的还是比较全的：

ACM题目中输入数据的处理（C语言版）_迂者-贺利坚的博客-CSDN博客_算法中循环输入用例

Code

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdbool.h>
  5. #include <math.h>
  6. #include <float.h>
  7.  
  8. #define CEILING_POS(X) ((X-(int)(X)) > 0 ? (int)(X+1) : (int)(X))
  9. #define CEILING_NEG(X) ((X-(int)(X)) < 0 ? (int)(X-1) : (int)(X))
  10. #define CEILING(X) ( ((X) > 0) ? CEILING_POS(X) : CEILING_NEG(X) )
  11.  
  12. #define MIN(a, b) ((a) < (b)) ? (a) : (b)
  13. #define MAX(a, b) ((a) > (b)) ? (a) : (b)
  14.  
  15. int cmpfunc (const void * a, const void * b) {
  16.    return ( *(int*)a - *(int*)b );
  17. }
  18. //qsort(dp, m+1, sizeof(int), cmpfunc);
  19.  
  20. bool find(int N, int M, char matrix[][M], bool visited[][M], int x, int y,
  21.           char* s, int k) {
  22.     if (matrix[x][y] != s[k]) {
  23.         return false;
  24.     } else if (k == strlen(s) - 1) {
  25.         return true;
  26.     }
  27.     printf("%d %d\n", x,y);
  28.     visited[x][y] = true;
  29.     int dic[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  30.     bool result = false;
  31.     for (int i = 0; i < 4; ++i) {
  32.         int newx = x + dic[i][0], newy = y + dic[i][1];
  33.         if (newx >= 0 && newx < N && newy >= 0 && newy < M) {
  34.             
  35.             if (!visited[newx][newy]) {
  36.                 printf("%d %d\n", newx,newy);
  37.                 bool found = find(N, M, matrix, visited, newx, newy, s, k + 1);
  38.                 if (found) {
  39.                     result = true;
  40.                     break;
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     visited[x][y] = false;
  46.     return result;
  47. } 
  48.  
  49. int main () {
  50.     int N, M;
  51.     scanf("%d %d", &M, &N);
  52.     char word[1000];
  53.     scanf("%s", word);
  54.     char matrix[N][M];
  55.     for (int i = 0; i < N; ++i) {
  56.         for (int j = 0; j < M; ++j) {
  57.             scanf("%c", &matrix[i][j]);
  58.         }
  59.     }
  60.     
  61.     bool visited[N][M];
  62.     for (int i = 0; i < N; ++i) {
  63.         for (int j = 0; j < M; j++) {
  64.             visited[i][j] = false;
  65.         }
  66.     }
  67.     find( N,M, matrix, visited, 2, 1, word, 0);
  68.     /*
  69.     for (int i = 0; i < N; ++i) {
  70.         for (int j = 0; j < M; j++) {
  71.             bool found = find( N,M, matrix, visited, i, j, word, 0);
  72.             if (found) {
  73.                 printf("%d %d\n", i + 1, j + 1);
  74.                 return;
  75.             }
  76.         }
  77.     }*/
  78.     printf("NO\n");
  79. 5 5
  80. HELLOWORLD
  81. CPUCY
  82. EKLQH
  83. CHELL
  84. LROWO
  85. DGRBC
  86.  
  87.     return 0;
  88.  
  89. }

要求

时间限制：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)

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/99447
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号