Google APAC 2017 round A problem B Rain

Revision en1, by spontaneously, 2016-07-10 11:39:25

Problem

I used dfs but I'm getting incorrect answer. here's my code:

import java.util.*;

class testClass {

static boolean[][] visited;
static int[] dx ={0,0,-1,1};
static int[] dy = {-1,1,0,0};
static int[][]  b;
static int r;
static int c;
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int T = in.nextInt();
    in.nextLine();
    for (int f = 1; f <= T; f++) {
        System.out.print("Case #" + f + ": ");
        r = in.nextInt();
        c = in.nextInt();
        b = new int[r][c];
        for (int i = 0; i <r ; i++) {
            for (int j = 0; j <c ; j++) {
                b[i][j] = in.nextInt();
            }
        }
        ArrayList<Integer> min;
        long ans =0;
        visited = new boolean[r][c];
        for (int i  =1; i <r-1 ; i++) {
            for (int j = 1; j <c-1 ; j++) {

                if(!visited[i][j]){
                    min=new ArrayList<Integer>();
                    min.add(Integer.MAX_VALUE);
                    min.add(0);
                    dfs(i,j,min);
                    ans += (long)(((long)min.get(0))*((long)min.get(1)));
                }
            }
        }
        System.out.println(ans);

    }
}
public static void dfs(int i, int j, ArrayList<Integer> min){
    visited[i][j] = true;
    min.set(1,min.get(1)+1);
    for (int k = 0; k < 4; k++) {
        int x = i+dx[k];
        int y = j+dy[k];
        if(b[i][j]==b[x][y]){
            if(!isValid(x,y)){

                min.set(0,0);
            }
            else if(!visited[x][y]){
                dfs(x,y,min);
            }
        }
        else if(b[i][j]>b[x][y]){
            min.set(0,0);
        }
        else if(b[i][j]<b[x][y]){
            if(min.get(0).compareTo(new Integer(b[x][y]-b[i][j]))>0) min.set(0,b[x][y]-b[i][j]);
        }
    }
}
public static boolean isValid(int i, int j){
    if(i<1||i>=r-1 ) return false;
    if(j<1||j>=c-1) return false;
    return true;
}

}

Tags apac 2017, google apac, apactest 217

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English spontaneously 2016-07-10 12:08:44 2210
en1 English spontaneously 2016-07-10 11:39:25 2407 Initial revision (published)