{"id":977,"date":"2025-12-16T04:11:08","date_gmt":"2025-12-15T20:11:08","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=977"},"modified":"2025-12-16T04:11:08","modified_gmt":"2025-12-15T20:11:08","slug":"leetcode-79-%e5%8d%95%e8%af%8d%e6%90%9c%e7%b4%a2","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=977","title":{"rendered":"LeetCode 79 – \u5355\u8bcd\u641c\u7d22"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h1>\n

\u7ed9\u5b9a\u4e00\u4e2a m x n \u4e8c\u7ef4\u5b57\u7b26\u7f51\u683c board \u548c\u4e00\u4e2a\u5b57\u7b26\u4e32\u5355\u8bcd word \u3002\u5982\u679c word \u5b58\u5728\u4e8e\u7f51\u683c\u4e2d\uff0c\u8fd4\u56de true \uff1b\u5426\u5219\uff0c\u8fd4\u56de false \u3002<\/p>\n

\u5355\u8bcd\u5fc5\u987b\u6309\u7167\u5b57\u6bcd\u987a\u5e8f\uff0c\u901a\u8fc7\u76f8\u90bb\u7684\u5355\u5143\u683c\u5185\u7684\u5b57\u6bcd\u6784\u6210\uff0c\u5176\u4e2d\u201c\u76f8\u90bb\u201d\u5355\u5143\u683c\u662f\u90a3\u4e9b\u6c34\u5e73\u76f8\u90bb\u6216\u5782\u76f4\u76f8\u90bb\u7684\u5355\u5143\u683c\u3002\u540c\u4e00\u4e2a\u5355\u5143\u683c\u5185\u7684\u5b57\u6bcd\u4e0d\u5141\u8bb8\u88ab\u91cd\u590d\u4f7f\u7528\u3002<\/p>\n

\u9898\u76ee\u5206\u6790<\/h1>\n

DFS\uff0c\u6bcf\u5c42\u5bf9\u5e94\u5355\u8bcd\u4e2d\u7684\u4e00\u4e2a\u4e0b\u6807\uff0c\u4f7f\u7528visited\u6570\u7ec4\u6807\u8bb0\u54ea\u4e2a\u4f4d\u7f6e\u8bbf\u95ee\u8fc7<\/p>\n

Java<\/h1>\n
private int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\nprivate boolean exist = false;\n\npublic boolean exist(char[][] board, String word) {\n    int m = board.length;\n    int n = board[0].length;\n    for (int i = 0; i < board.length; i++) {\n        for (int j = 0; j < board[i].length; j++) {\n            dfs(board, new boolean[m][n], i, j, word, 0);\n            if (exist) {\n                return true;\n            }\n        }\n    }\n    return false;\n}\n\nprivate void dfs(char[][] board, boolean[][] visited, int i, int j, String word, int index) {\n    int m = board.length;\n    int n = board[0].length;\n    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index) || exist) {\n        return;\n    }\n    if (index == word.length() - 1) {\n        exist = true;\n        return;\n    }\n    visited[i][j] = true;\n    for (int[] dir : directions) {\n        int newI = i + dir[0];\n        int newJ = j + dir[1];\n        dfs(board, visited, newI, newJ, word, index + 1);\n    }\n    visited[i][j] = false;\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
private val directions = arrayOf(intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(0, -1))\nprivate var exist = false\n\nfun exist(board: Array<CharArray>, word: String): Boolean {\n    for (i in board.indices) {\n        for (j in board[0].indices) {\n            dfs(board, word, i, j, 0, Array(board.size) { BooleanArray(board[0].size) })\n            if (exist) {\n                return true\n            }\n        }\n    }\n    return false\n}\n\nprivate fun dfs(board: Array<CharArray>, word: String, i: Int, j: Int, index: Int, visited: Array<BooleanArray>) {\n    if (i !in board.indices || j !in board[0].indices || board[i][j] != word[index] || visited[i][j] || exist) {\n        return\n    }\n    if (index == word.length - 1) {\n        exist = true\n        return\n    }\n    visited[i][j] = true\n    for (dir in directions) {\n        dfs(board, word, i + dir[0], j + dir[1], index + 1, visited)\n    }\n    visited[i][j] = false\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a m x n \u4e8c\u7ef4\u5b57\u7b26\u7f51\u683c board \u548c\u4e00\u4e2a\u5b57\u7b26\u4e32\u5355\u8bcd word \u3002\u5982\u679c word \u5b58\u5728\u4e8e […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[11,20,90,83],"class_list":["post-977","post","type-post","status-publish","format-standard","hentry","category-algo","tag-dfs","tag-leetcode","tag-90","tag-83"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/977","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=977"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/977\/revisions"}],"predecessor-version":[{"id":978,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/977\/revisions\/978"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=977"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}