Ex12 矩阵中的路径

问题描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b”,”c”,”e”], [”s”,”f”,”c”,”s”], [“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

问题分析

这个问题想来是很简单的，方法概述如下：

  1. 得到第一个等于字符串的字符及其位置，标记一个访问标志；
  2. 查找上下左右的字符，是否是字符串的下一个字符，如果是的话，标记一个访问标志；
  3. 直到字符串终了。

但是，这里面有很多细节问题需要注意的，特别是返回true或false的时候，所有该判断的条件是否都判断了？

代码

bool exist_helper (char **board, int start_row, int row_size, int start_col,
                   int col_size, char *word, bool **visited);

bool
exist (char **board, int boardSize, int *boardColSize, char *word)
{
  if (!board || !(*board) || boardSize <= 0 || *boardColSize <= 0 || !word
      || *word == '\0')
    return false;
  bool **visited = (bool **)malloc (boardSize * sizeof (bool *));
  for (int i = 0; i < boardSize; ++i)
    {
      visited[i] = (bool *)malloc (*boardColSize * sizeof (bool));
    }
  for (int i = 0; i < boardSize; ++i)
    {
      for (int j = 0; j < *boardColSize; ++j)
        {
          visited[i][j] = false;
        }
    }
  for (int i = 0; i < boardSize; ++i)
    {
      for (int j = 0; j < *boardColSize; ++j)
        {
          if (board[i][j] == *word)
            {
              if (exist_helper (board, i, boardSize, j, *boardColSize, word,
                                visited))
                {
                  for (int i = 0; i < boardSize; ++i)
                    {
                      free (visited[i]);
                    }
                  free (visited);
                  return true;
                }
            }
        }
    }
  for (int i = 0; i < boardSize; ++i)
    {
      free (visited[i]);
    }
  free (visited);

  return false;
}

bool
exist_helper (char **board, int start_row, int row_size, int start_col,
              int col_size, char *word, bool **visited)
{
  if (*word == '\0')
    return true;
  if (start_row < 0 || start_row >= row_size || start_col < 0
      || start_col >= col_size)
    return false;
  if (board[start_row][start_col] != *word)
    return false;
  if (visited[start_row][start_col])
    return false;

  visited[start_row][start_col] = true;

  // up
  if (exist_helper (board, start_row - 1, row_size, start_col, col_size,
                    word + 1, visited))
    return true;
  // down
  if (exist_helper (board, start_row + 1, row_size, start_col, col_size,
                    word + 1, visited))
    return true;
  // left
  if (exist_helper (board, start_row, row_size, start_col - 1, col_size,
                    word + 1, visited))
    return true;
  // right
  if (exist_helper (board, start_row, row_size, start_col + 1, col_size,
                    word + 1, visited))
    return true;

  visited[start_row][start_col] = false;
  return false;
}

结果

执行结果：通过

执行用时：24 ms, 在所有 C 提交中击败了85.71%的用户

内存消耗：6.6 MB, 在所有 C 提交中击败了21.91%的用户

备注

bool **visited = (bool **)malloc (boardSize * sizeof (bool *));
for (int i = 0; i < boardSize; ++i)
  {
    visited[i] = (bool *)malloc (*boardColSize * sizeof (bool));
  }
for (int i = 0; i < boardSize; ++i)
  {
    for (int j = 0; j < *boardColSize; ++j)
      {
        visited[i][j] = false;
      }
  }
for (int i = 0; i < boardSize; ++i)
  {
    free (visited[i]);
  }
free (visited);