Tag: 2018

Referring to this question: http://usaco.org/index.php?page=viewproblem2&cpid=836

Hi! So I’m working on this problem, and my approach was to search ever possible ways, but it time out on one case:

And here is my code:

import java.io.*;
import java.util.*;

public class main {
    public static int()() grid;
    public static boolean()() went, went2;
    public static int cnt;
    
    public static void dfs1(int x, int y, int wanted) {
        if(x < 0 || y < 0 || x >= grid.length ||  y >= grid.length) {
            return;
        }
        
        if(went(x)(y) || grid(x)(y) != wanted) {
            return;
        }
        went(x)(y) = true;
        cnt++;
        
        dfs1(x + 1, y, wanted);
        dfs1(x - 1, y, wanted);
        dfs1(x, y + 1, wanted);
        dfs1(x, y - 1, wanted);
    }
    
    public static void dfs2(int x, int y, LinkedList<Integer> wanted) {
        if(x < 0 || y < 0 || x >= grid.length || y >= grid.length) {
            return;
        }
        
        if(went2(x)(y)) {
            return;
        }else if(!wanted.contains(grid(x)(y)) && wanted.size() >= 2) {
            return;
        }else if(wanted.size() < 2 && !wanted.contains(grid(x)(y))) {
            wanted.add(grid(x)(y));
        }
        
        cnt++;
        if(wanted.size() < 2) {
            went(x)(y) = true;
        }
        went2(x)(y) = true;
        
        dfs2(x + 1, y, wanted);
        dfs2(x - 1, y, wanted);
        dfs2(x, y + 1, wanted);
        dfs2(x, y - 1, wanted);
    }
    
    
    public static void main(String() args) throws IOException{
        //BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader input = new BufferedReader(new FileReader("multimoo.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("multimoo.out")));
        
        StringTokenizer st = new StringTokenizer(input.readLine());
        int n = Integer.parseInt(st.nextToken());
        grid = new int(n)(n);
        went = new boolean(n)(n);
        went2 = new boolean(n)(n);
        
        for(int i = 0;i<n;i++) {
            st = new StringTokenizer(input.readLine());
            
            for(int j = 0;j<n;j++) {
                int num = Integer.parseInt(st.nextToken());
                grid(i)(j) = num;
            }
            
        }
        
        
        int best = 0;
        //int best2 = 0;
        
        for(int i = 0;i<n;i++) {
            for(int j = 0;j<n;j++) {
                if(!went(i)(j)) {
                    cnt = 0;
                    dfs1(i, j, grid(i)(j));
                    if(cnt > best) {
        //              best2 = best;
                        best = cnt;
                    }
                }
            }
        }
        
        //best2 += best;
        //System.out.println(best);
        out.println(best);
        best = 0;
        
        went = new boolean(n)(n);
        
        
        for(int i = 0;i<n;i++) {
            for(int j = 0;j<n;j++) {
                if(!went(i)(j)) {
                    cnt = 0;
                    LinkedList<Integer> wanted = new LinkedList<Integer>();
                    wanted.add(grid(i)(j));
                    went2 = new boolean(n)(n);
                    dfs2(i, j, wanted);
                    best = Math.max(best, cnt);
                }
            }
        }
        
        //System.out.println(best);
        out.println(best);
        out.close();
    }

}

So my question was, how can I pass the one case? I sure I just need a little change somewhere, since I’m only having a time limit exceeded on one case. Thanks!