Introduction
给你一个大小为m*n的矩阵Mine表示矿场，里面有丰富的宝石。Mine(i,j)若大于0，表示该点存在宝石，其值为宝石价值；若等于0，表示的是不可进入的区域；若小于-1表示危险区域。当你选择一个点挖宝石的时候，你可以把相邻（上下左右)的宝石也挖出来。但是注意，任意你挖出宝石的点不可与危险区域相邻。
请计算你从某一点作为起点能挖出的最大财富，财富等于你挖出宝石价值的总和。
Input
第一行给出m和n，第二行给出Mine的一维表示
1<=m,n<=50
-1<=Mine[i][j]<=10
Output
整数最大价值
Sample
input
3 3 0 1 0 1 1 1 0 1 0
output
5
Solution
import java.util.Scanner; public class Main { static void dfs(int x,int y){ if(x<0||x>n-1||y<0||y>m-1||flag[x][y])return; score+=arr[x][y]; if(score>max)max=score; flag[x][y]=true; for(int k=0;k<4;k++){ dfs(x+X[k],y+Y[k]); } } static int n,m,max=0,score=0; static int[][] arr; static boolean[][] flag; static int[] X={1,0,-1,0}; static int[] Y={0,1,0,-1}; public static void main(String[] args) { Scanner s=new Scanner(System.in); n=s.nextInt(); m=s.nextInt(); arr=new int[n][m]; flag =new boolean[n][m]; for (int i=0;i<n;i++){ for (int j=0;j<m;j++){ arr[i][j]=s.nextInt(); } } for (int i=0;i<n;i++){ for (int j=0;j<m;j++){ if(arr[i][j]==0)flag[i][j]=true; if(arr[i][j]==-1){ flag[i][j]=true; for(int k=0;k<4;k++){ if(i+X[k]>=0&&i+X[k]<n&&j+Y[k]>=0&&j+Y[k]<m) flag[i+X[k]][j+Y[k]]=true; } } } } // for (boolean[] a:flag){ // System.out.println(Arrays.toString(a)); // } for (int i=0;i<n;i++){ for (int j=0;j<m;j++){ score=0; dfs(i,j); } } System.out.println(max); } }
Experience
一次普通的dfs，刚开始忘记了score=0
