# Help needed! Where is my Java code wrong in RISK problem?

I tried to solve the RISK problem of the April Starters contest using the following approach :

We iterate through every element of the 2d world map matrix, and if it is a land element, we count THAT ELEMENT as well as its NEIGHBORING ELEMENTS which are also land elements using a recursive approach, thus returning count of connected elements.

The solution is giving Runtime Error on most of the hidden test cases and I am unable to understand where am I going wrong here. Can anyone help in pointing that out ?

Here 's my submission :

https://www.codechef.com/viewsolution/45425456

Dude!!!

``````for( int i = 0; i<n; i++ ){
int num = scn.nextInt();
for( int j = 1; j <= m; j++ ){
map[i][m-j] = (int)( ( num% Math.pow(10, j) ) / Math.pow(10, j-1));
}
}
``````

You are taking string into Integer. Note that strings can be very huge. Take them into strings instead of Integers.

Okay, that makes sense. But then, converting it into a character array is still producing Runtime as well as Time Limit Errors.

https://www.codechef.com/viewsolution/45499049

I added some stuff and executed it.

The Code
``````/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static int matching(char[][] array, boolean[][] check, int n, int m, int x, int y ){
System.err.println(x + " " + y);
if( array[x][y] == '0' || check[x][y] == true ){
check[x][y] = true;
return 0;
}

int sum = 1;
check[x][y] = true;
if( x-1 >= 0  ){ sum += matching(array,check, n, m, x-1, y); }
if( x+1 < m  ){ sum += matching(array,check, n, m, x+1, y); }
if( y-1 >= 0  ){ sum += matching(array,check, n, m, x, y-1); }
if( y+1 < n ){ sum += matching(array,check, n, m, x, y+1); }

return sum;
}

public static void main (String[] args) throws java.lang.Exception
{
Scanner scn = new Scanner(System.in);
int T = scn.nextInt();

while( T-- > 0 ){
int n = scn.nextInt();
int m = scn.nextInt();
char[][] map = new char[n][m];
boolean[][] check = new boolean[n][m];

for( int i = 0; i<n; i++ ){
String num = scn.next();
map[i] = num.toCharArray();
}

for( int i = 0; i < n; i++ ){
for( int j = 0; j < m; j++ ){
if( !check[i][j] && map[i][j] == '1'){
int nsum = matching(map, check, n, m, i, j);
if( nsum != 0 ){ sums.add(nsum); }
}
}
}

Collections.sort( sums, Collections.reverseOrder() );
int res = 0;
for( int i = 1; i < sums.size(); i = i+2 ){
res += sums.get(i);
}
System.out.println(res);
System.err.println();
}
}
}
``````

STDIN

``````3
4 4
1001
0110
0110
1001
2 2
11
11
3 3
100
010
001
``````

STDOUT

``````2
0
1
``````

STDERR

``````0 0
1 0
0 1
0 3
1 3
0 2
1 1
0 1
2 1
1 1
3 1
2 0
2 2
1 2
0 2
2 2
1 1
1 3
3 2
2 1
2 3
1 0
1 2
3 0
2 0
3 1
3 3
2 3
3 2

0 0
1 0
0 0
1 1
0 1
1 1
0 0
1 0
0 1

0 0
1 0
0 1
1 1
0 1
2 1
1 0
1 2
2 2
1 2
2 1
``````

What do you infer from this?
You are visiting the same node again and again. For strong test cases, the recursion depth is so huge causing RTE. You need to visit a cell only if the following conditions hold true.

1. You have not visited the cell
2. The cell you are gonna visit is ‘1’.

Make these changes and try again.

I really appreciate your effort. However, I made the changes and still that doesn’t seem to be the case. It’s still showing the same errors :

https://www.codechef.com/viewsolution/45505231

You didn’t. I made the changes and here’s ACfied Code.

ACfied Code
``````/*
Author: Chitturi Sai Suman
Created: 2021-04-28 21:42:16
*/
// 57:69:74:68:20:4C:4F:56:45

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

public class Main {

static Scanner io;
static int dc[] = {1, 0, 0, -1, -1, -1, 1, 1};
static int dr[] = {0, 1, -1, 0, -1, 1, -1, 1};

public static int visit(char s[][], boolean visited[][], int i, int j, int n, int m) {
int score = 1;
visited[i][j] = true;
for(int k = 0; k < 4; k++) {
if(i + dc[k] >= 0 && i + dc[k] < n && j + dr[k] >= 0 && j + dr[k] < m) {
if(!visited[i + dc[k]][j + dr[k]] && s[i + dc[k]][j + dr[k]] == '1') {
score += visit(s, visited, i + dc[k], j + dr[k], n, m);
}
}
}
return score;
}

public static void solve() {
// Solve Test Cases here
//
int n = io.nextInt();
int m = io.nextInt();
char s[][] = new char[n][m];
for(int i = 0; i < n; i++) {
s[i] = io.next().toCharArray();
}
boolean visited[][] = new boolean[n][m];
for(int i = 0; i < n; i++) {
Arrays.fill(visited[i], false);
}
ArrayList<Integer> scores = new ArrayList<Integer>();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!visited[i][j] && s[i][j] == '1') {
scores.add(visit(s, visited, i, j, n, m));
}
}
}
Collections.sort(scores, Collections.reverseOrder());
int ans = 0;
for(int i = 1; i < scores.size(); i += 2) {
ans += scores.get(i);
}
System.out.println(ans);
}

public static void main(String[] args) {

io = new Scanner(System.in);
int testcases = 0;

// testcases++;

if(testcases == 0)
testcases = io.nextInt();

for(int test = 0; test < testcases; test++) {

// io.print("Case #" + (test + 1) + ": ");

solve();

}
}
}
``````

That’s great ! I had to finally change my approach and make it similar to yours to arrive at an accepted code. One thing I learned was that the use of LinkedList instead of an ArrayList was heavily responsible for the TLE. Wasn’t noticing that earlier.

Thanks a lot for helping me out with this . Here’s my version of the ACfied code :

https://www.codechef.com/viewsolution/45515081