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!