2023华为od统一考试B卷【宜居星球改造计划】C语言实现

清疚 2023-10-10 19:56 13阅读 0赞

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

## 题目 ##

> 2XXX年，人类通过对火星的大气进行宜居改造分析，使得火星已在理论上具备人类宜居的条件，由于技术原因，无法一次性将火星大气全部改造，只能通过局部处理形式，假设将火星待改造的区域为row \* column的网格每个网格有3个值，宜居区、可改造区、死亡区，使用YES、NO、NA代替，YES表示该网格已经完成大气改造，NO表示该网格未进行改造，后期可进行改造，NA表示死亡区，不作为判断是否改造完成的宜居，无法穿过  
> 初始化下，该区域可能存在多个宜居区，并且每个宜居区能同时在每个太阳日单位向上下左右四个方向的相邻格子进行扩散，自动将4个方向相邻的真空区改造成宜居区;请计算这个待改造区域的网格中，可改造区是否能全部变成宜居区，如果可以，则返回改造的太阳日天数，不可以则返回-1。
> 
> **输入描述:**  
> 输入row\*column个网格数据，每个网格值枚举值如下: YES，NO，NA，样例:  
> YES YES NO  
> NO NO NO  
> NA NO YES  
> **输出描述:**  
> 可改造区是否能全部变成宜居区，如果可以，则返回改造的太阳日天数，不可以则返回-1.  
> 补充说明:  
> grid\[i\]只有3种情况，YES、NO、NA  
> row == grid.length, column == grid\[i\].length, 1 <= row, column <= 8
> 
> **示例1  
> 输入:**  
> YES YES NO  
> NO NO NO  
> YES NO NO  
> **输出:**
> 
> **2  
> 说明:**  
> 经过2个太阳日，完成宜居改造.
> 
> **示例2  
> 输入:**  
> YES NO NO NO
> 
> NO NO NO NO  
> NO NO NO NO  
> NO NO NO NO  
> **输出:**
> 
> **6  
> 说明:**  
> 经过6个太阳日，可完成改造
> 
>   
> **示例3  
> 输入:**
> 
> NO NA  
> **输出:**
> 
> \-1
> 
> **说明:**  
> 无改造初始条件，无法进行改造
> 
>   
> **示例4  
> 输入:**  
> YES NO NO YES
> 
> NO NO YES NO
> 
> NO YES NA NA
> 
> YES NO NA NO  
> 输出:
> 
> \-1  
> 说明:
> 
> 右下角的区域，被周边三个死亡区挡住，无法实现改造
> 
> ![4e1b6fb0df0748c085f4713de9777688.jpeg][]

## 思路 ##

> 1：好恶心这个题目，不给定输入的行列数，还要自己判断。
> 
> 2：典型的一个多源BFS问题，可以参考 [leetcode][]上一个很类似的题目，题解区《宫水三叶》的讲解非常牛逼，可以参考下。

##  ##

## Code ##

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>
    #include <math.h>
    #include <limits.h>
    #include <float.h>
    #include <stdint.h>
    #include <ctype.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);
    
    
    typedef struct {
        int x;
        int y;
    } Position;
    
    Position create(int x, int y) {
        Position coord;
        coord.x = x;
        coord.y = y;
        return coord;
    }
    
    int count = 0;
    int front = 0, rear = 0;
    Position q[100 * 100];
    void bfs(char*** matrix, int i, int j,int m, int n) {
        if (i - 1 >= 0 && strcmp(matrix[i - 1][j], "NO") == 0) {
            strcpy(matrix[i - 1][j], "YES");
            q[rear++] = create(i - 1, j);
            count++;
        }
        if (i + 1 < m && strcmp(matrix[i + 1][j], "NO") == 0) {
            strcpy(matrix[i + 1][j], "YES");
            q[rear++] = create(i + 1, j);
            count++;
        }
        if (j - 1 >= 0 && strcmp(matrix[i][j - 1], "NO") == 0) {
            strcpy(matrix[i][j - 1], "YES");
            q[rear++] = create(i, j - 1);
            count++;
        }
        if (j + 1 < n && strcmp(matrix[i][j + 1], "NO") == 0) {
            strcpy(matrix[i][j + 1], "YES");
            q[rear++] = create(i, j + 1);
            count++;
        }
    }
    
    int main() {
        int m, n;
        //构造输入矩阵
        char*** matrix = (char***)malloc(100 * sizeof(char**));
        
        int need = 0;
        for (int i = 0; i < 100; i++) {
            matrix[i] = (char**)malloc(100 * sizeof(char*));
            for (int j = 0; j < 100; j++) {
                matrix[i][j] = (char*)malloc(100 * sizeof(char));
            }
        }
    
        int row = 0;
    
        //输入处理
        char input_str[100];
        while (fgets(input_str, sizeof(input_str), stdin) != NULL) {
            int len = strlen(input_str);
            if (input_str[len - 1] == '\n') {
                input_str[len - 1] = '\0';
            }
    
            if (strlen(input_str) == 0) {
                break;
            }
    
            char* token;
            int col = 0;
            //空格分割
            token = strtok(input_str, " ");
    
            while (token != NULL) {
                strcpy(matrix[row][col], token);
                if (strcmp(matrix[row][col], "NO") == 0) {
                    need++;
                } else if (strcmp(matrix[row][col], "YES") == 0) {
                    q[rear++] = create(row, col);
                }
                col++;
                token = strtok(NULL, " ");
            }
    
            if (n == 0) {
                n = col;
            }
            row++;
        }
    
        m = row;
        int res = 0;
    
        while (front != rear) {
            int sz = rear - front;
            for (int i = 0; i < sz; i++) {
                Position top = q[front++];
                //BFS 遍历
                bfs(matrix, top.x, top.y,m,n);
            }
            if (front != rear) {
                res++;
            }
        }
    
        if (count == need) {
            printf("%d\n", res);
        } else {
            printf("-1\n");
        }
    
    
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                free(matrix[i][j]);
            }
            free(matrix[i]);
        }
        free(matrix);
        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
[4e1b6fb0df0748c085f4713de9777688.jpeg]: https://img-blog.csdnimg.cn/4e1b6fb0df0748c085f4713de9777688.jpeg
[leetcode]: https://leetcode.cn/problems/as-far-from-land-as-possible/