单词搜索黄金矿工

本文主要是介绍单词搜索黄金矿工，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

79. 单词搜索

中等

1.7K

相关企业

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

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

class Solution {boolean[][] check;char[] word;public boolean exist(char[][] board, String _word) {check = new boolean[board.length][board[0].length];word = _word.toCharArray();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == word[0]) {check[i][j] = true;if (dfs(board, i, j, word, 1)) return true; //該路徑找到了check[i][j] = false;}}}return false;}int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};boolean dfs(char[][] board, int i, int j, char[] word, int pos) {if (pos == word.length) {return true;}//向量數組for (int k = 0; k < 4; k++) {int x = dx[k] + i;int y = dy[k] + j;if (x >= 0 && y >= 0 && x < board.length && y < board[0].length && board[x][y] == word[pos] && !check[x][y]) {check[x][y] = true;if (dfs(board, x, y, word, pos + 1)) return true;check[x][y] = false;}}return false;}
}

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],[5,8,7],[0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。
class Solution {boolean[][] check;int ret = 0;int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};public int getMaximumGold(int[][] grid) {int m = grid.length;int n = grid[0].length;check = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] != 0) {check[i][j] = true;dfs(grid, i, j, grid[i][j]);check[i][j] = false;}}}return ret;}void dfs(int[][] grid, int x, int y, int path) {ret = Math.max(ret, path);for (int k = 0; k < 4; k++) {int newX = x + dx[k];int newY = y + dy[k];if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && !check[newX][newY] && grid[newX][newY] != 0) {check[newX][newY] = true;dfs(grid, newX, newY, path + grid[newX][newY]);check[newX][newY] = false; // 回溯}}}
}