Google Apac Test Round Dynamic Grid[Java Solution] using DFS

Google Apac Test Round Dynamic Grid[Java Solution] using DFS

Problem Statement:-https://code.google.com/codejam/contest/11214486/dashboard

Hint:- Apply DFS.

Java Program:-

/**

 * @(#)DynamicGrid.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2016/1/23

 */

import java.io.*;

import java.util.*;

class DynamicGrid {

    public static void main(String args[])throws IOException{

   

    BufferedReader br=new BufferedReader(new FileReader("A-large-practice.in"));

    PrintWriter out=new PrintWriter(new FileWriter("output-large.out"));

   

    int T=Integer.parseInt(br.readLine());

    int nt=1;

    while(T--!=0){

    out.println("Case #"+(nt++)+":");

    String inp[]=br.readLine().split(" ");

    int R=Integer.parseInt(inp[0]);

    int C=Integer.parseInt(inp[1]); 

   

    int grid[][]=new int[R][C];

   

    String str;

    for(int i=0;i<R;i++){

    str=br.readLine();

    for(int j=0;j<C;j++){

    grid[i][j]=Integer.parseInt(str.charAt(j)+"");

    }

    }

   

    int nQ=Integer.parseInt(br.readLine());

   

    while(nQ--!=0){

   

    inp=br.readLine().split(" ");

   

    if(inp[0].charAt(0)=='Q'){

    out.println(solve(grid));

    }else{

    int x=Integer.parseInt(inp[1]);

    int y=Integer.parseInt(inp[2]);

    int z=Integer.parseInt(inp[3]);

   

    grid[x][y]=z;

    }

   

    }

    }

    out.close();

    }

    

    public static int solve(int grid[][]){

    int ans=0;

    int newGrid[][]=new int[grid.length][grid[0].length];

   

    for(int i=0;i<grid.length;i++){

    for(int j=0;j<grid[0].length;j++){

    newGrid[i][j]=grid[i][j];

    }

    }

   

    for(int i=0;i<grid.length;i++){

    for(int j=0;j<grid[0].length;j++){

    if(newGrid[i][j]==1){

    dfs(newGrid,i,j);

    ans++;

    //printGrid(newGrid);

    }

    }

    }

    return ans;

    }

    

    public static void dfs(int grid[][],int i,int j){

   

    grid[i][j]=5;

   

   

   

    if(i-1>=0&&grid[i-1][j]==1){

    grid[i-1][j]=5;

    dfs(grid,i-1,j);

    }

    if(j-1>=0&&grid[i][j-1]==1){

    grid[i][j-1]=5;

    dfs(grid,i,j-1);

    }

    if(i+1<grid.length&&grid[i+1][j]==1){

    grid[i+1][j]=5;

    dfs(grid,i+1,j);

    }

    if(j+1<grid[0].length&&grid[i][j+1]==1){

    grid[i][j+1]=5;

    dfs(grid,i,j+1);

    }

   

    }

    

}

Input:-

1

4 4

0101

0010

0100

1111

7

Q

M 0 2 1

Q

M 2 2 0

Q

M 2 1 0

Q

Output:-

Case #1:

4

2

2

2

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------