leetcode 79 검 은 offer 면접 문제 12. 행렬 의 경 로 를 가리킨다.

문제: 행렬 에 문자열 의 모든 문 자 를 포함 하 는 경로 가 있 는 지 판단 하기 위해 함 수 를 설계 하 십시오.경 로 는 행렬 의 임 의 한 칸 에서 시작 할 수 있 고 모든 단 계 는 행렬 에서 왼쪽, 오른쪽, 위, 아래 로 한 칸 을 이동 할 수 있다.한 경로 가 행렬 의 한 칸 을 지나 면 이 경 로 는 다시 이 칸 에 들 어 갈 수 없습니다.아래×4 의 행렬 에는 문자열 'bfce' 의 경로 가 포함 되 어 있 습 니 다.

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

그러나 행렬 에는 문자열 'abfb' 의 경로 가 포함 되 어 있 지 않 습 니 다. 문자열 의 첫 번 째 문자 b 가 행렬 의 첫 번 째 줄 두 번 째 칸 을 차지 한 후에 경 로 는 이 칸 에 다시 들 어 갈 수 없습니다.

   1：

  ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  ：true
   2：

  ：board = [["a","b"],["c","d"]], word = "abcd"
  ：false

알림: 1 < = board. length < = 2001 < = board [i]. length < = 200
문제 풀이 방향: 1. 주어진 행렬 에서 워드 의 첫 번 째 문 자 를 찾 고 찾 으 면 다음 에 찾 습 니 다. 찾 지 못 하면 return false;2. 다음 단 어 를 어떻게 찾 는 지 는 몇 가지 상황 으로 나 누 어 토론 해 야 합 니 다. 현재 문자 의 위, 아래, 왼쪽, 오른쪽, 워드 와 일치 하 는 다음 문 자 를 순서대로 찾 아야 합 니 다.(이 단 계 는 '또는' 주어진 조건 을 사용 해 야 합 니 다).일치 하 는 문자 마다 이전 문 자 를 반복 하지 않도록 이전 문 자 를 '/' 로 설정 할 수 있 습 니 다.워드 가 모두 검 사 될 때 까지 순서대로 아래로 재 귀적 으로 찾 습 니 다.3. 검 사 를 마 친 후 거 슬러 올 라 가 '/' 로 설 정 된 문 자 를 업데이트 합 니 다. 워드 를 찾 으 면 트 루 로 돌아 갈 수 있 습 니 다. 찾 지 못 하면 첫 번 째 문 자 를 바 꾸 어 계속 찾 을 수 있 습 니 다.
코드 구현:

bool DFS(char** board, int row, int col, char* word, int x, int y){
     
    if (* word == '\0'){
                 //      word     ，     
        return true;
    }
    if (x < 0 || x >= row || y < 0 || y >= col || board[x][y] != * word){
     
        return false;       //   、   ，       word    ，    word
    }
    board[x][y] = '/';      //   board         ，       ，      '\'
    bool res = DFS(board, row, col, word + 1, x + 1, y) ||
               DFS(board, row, col, word + 1, x - 1, y) ||
               DFS(board, row, col, word + 1, x, y + 1) ||
               DFS(board, row, col, word + 1, x, y - 1);    //       
    board[x][y] = * word;       //   '/' board    ，                 
    return res;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word){
     
    for (int x = 0; x < boardSize; x++){
     
        for (int y = 0; y < boardColSize[0]; y++){
           //  word      
            if (board[x][y] == word[0] && DFS(board, boardSize, boardColSize[0], word, x, y)){
     
                return true;        //    word                  
            }
        }
    }
    return false;
}

결론: 이런 유형의 문 제 는 매우 번 거 로 워 보이 지만 논리 적 으로 분석 하면 어렵 지 않 습 니 다. 알고리즘 은 결국 알고리즘 을 먼저 생각 한 다음 에 코드 로 실현 해 야 합 니 다. 한 걸음 한 걸음 먼저 첫 번 째 숫자 를 찾 은 다음 에 두 번 째 숫자 를 찾 아야 합 니 다.다른 하 나 는 재 귀 입 니 다. 재 귀 는 항상 저 를 돌아 가게 합 니 다. 재 귀 한 후에 절차 가 있 으 면 재 귀 를 다 실행 한 다음 에 다음 절 차 를 수행 해 야 합 니 다.