题解 | #牛群定位系统#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param board char字符型二维数组
 * @param boardRowLen int board数组行数
 * @param boardColLen int* board数组列数
 * @param words string字符串一维数组
 * @param wordsLen int words数组长度
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void dfs(char** board, int m, int n, int i, int j, int current, char* word,
         int** visited, int* flag) {
    if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] ||
            board[i][j] != word[current]) return;
    if (current + 1 == strlen(word)) {
        (*flag) = 1;
        return;
    }
    visited[i][j] = 1;
    dfs(board, m, n, i + 1, j, current + 1, word, visited, flag);
    dfs(board, m, n, i - 1, j, current + 1, word, visited, flag);
    dfs(board, m, n, i, j + 1, current + 1, word, visited, flag);
    dfs(board, m, n, i, j - 1, current + 1, word, visited, flag);
    visited[i][j] = 0;
}

void clearVisit(int** visited, int m, int n) {
    for (int i = 0; i < m; i++) memset(visited[i], 0, sizeof(int)*n);
}

char** findWords(char** board, int boardRowLen, int* boardColLen, char** words,
                 int wordsLen, int* returnSize ) {
    int m = boardRowLen, n = boardColLen[0];
    *returnSize = 0;
    char** res = malloc(sizeof(char*)*wordsLen);
    int** visited = malloc(sizeof(int*)*m);
    
    for (int i = 0; i < m; i++) {
        visited[i] = malloc(sizeof(int) * n);
        memset(visited[i], 0, sizeof(int)*n);
    }
    
    int flag, current, temp;
    for (int i = 0; i < wordsLen; i++) {
        for (int j = 0; j < m; j++) {
            temp = 0;
            for (int k = 0; k < n; k++) {
                if (board[j][k] == words[i][0]) {
                    flag = 0;
                    current = 0;
                    dfs(board, m, n, j, k, current, words[i], visited, &flag);
                    if (flag == 1) {
                        res[(*returnSize)] = malloc(sizeof(char) * (strlen(words[i]) + 2));
                        strcpy(res[(*returnSize)++], words[i]);
                        temp = 1;
                        break;
                    }
                }
            }
            if (temp) break;
        }
        clearVisit(visited, m, n);
    }
    return res;
}