2021-08-07 奇安信笔试题

编程题

第一题（跳过）

 三层for 暴力可过

编程题2

import java.util.*;


public class Solution2 {

  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * @param grid int整型二维数组 为n*m 的二维数组
   * @return int整型
   */
  int res = 0;
  int tmp = 0;

  public int getMaximumResource(int[][] grid) {
    // write code here
    if (grid.length == 0 || grid[0].length == 0) {
      return 0;
    }
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 0) {
          continue;
        }
        boolean[][] visit = new boolean[m][n];
        dfs(grid, i, j, visit);
      }
    }
    return res;
  }

  private void dfs(int[][] grid, int i, int j, boolean[][] visit) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0 || visit[i][j]) {
      res = Math.max(res, tmp);
      return;
    }

    visit[i][j] = true;
    tmp += grid[i][j];
    // right
    dfs(grid, i, j + 1, visit);
    // bottom
    dfs(grid, i + 1, j, visit);
    // left
    dfs(grid, i, j - 1, visit);
    // top
    dfs(grid, i - 1, j, visit);
    tmp -= grid[i][j];
    visit[i][j] = false;
  }
}