yashsaha555's blog

By yashsaha555, 3 years ago, In English

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);
	            }
	        }
	}
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't use Scanner, use BFS instead of DFS

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My code passed test cases with DFS(iterative) : https://cses.fi/paste/bbe61433a419cb2a9d44e0/