Link to the problem: https://cses.fi/problemset/task/1192/
I am getting time limit exceeded for Test cases #10 and #17 for this question. I am stuck with this for a long time and unable to figure it out as to why this is occuring. Need some help. My code is given below. Thanks in advance.
import java.util.*;
public class Crooms
{
static int direction[][]={{1,0},{0,1},{-1,0},{0,-1}};
static char ch[][]=new char[1001][1001];
static int vis[][]=new int[1001][1001];
static int n=0,m=0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
int count=0;
for(int i=0;i<n;i++)
{
ch[i]=sc.next().toCharArray();
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(ch[i][j]=='.' && vis[i][j]!=-1)
{
vis[i][j]=-1;
dfs(i,j);
count++;
}
}
}
System.out.println(count);
}
public static boolean boundary_check(int x, int y)
{
return x>=0 && y>=0 && x<n && y<m && ch[x][y]=='.' && vis[x][y]!=-1;
}
public static void dfs(int x, int y)
{
for(int i=0;i<4;i++)
{
int nx=x+direction[i][0];
int ny=y+direction[i][1];
if(boundary_check(nx,ny))
{
vis[nx][ny]=-1;
dfs(nx,ny);
}
}
}
}
https://mirror.codeforces.com/blog/entry/9108
Modified
You are checking boundary for (x,y) but calling dfs function for (x + direction[i][0] , y + direction[i][1] ) Attaching my code link , https://cses.fi/problemset/result/3253011/
Don't use Scanner, use BFS instead of DFS
My code passed test cases with DFS(iterative) : https://cses.fi/paste/bbe61433a419cb2a9d44e0/