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---------

Spoj Problem BITMAP- Bitmap[Java Solution]  using BFS

Problem Statement:-http://www.spoj.com/problems/BITMAP/

Hint:- Apply BFS.

Perform the BFS on the nodes where 1 is present and to elaborate(open) those nodes which are not 1 in BITMAP and calculate the distance and sotred in 2d array(i.e here sol[][]).If the solution array previously had any value(other than -1 i.e initially all -1) then minimum should be stored.

Java Program:-

/**

 * @(#)BITMAP.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/12/14

 */

import java.io.*;

import java.util.*;

class Node{

     int x;

     int y;

     int value;

    

     @Override

     public boolean equals(Object obj){

     Node n=(Node)obj;

     return this.x==n.x&&this.y==n.y;

     }

}

class BITMAP {

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

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

   

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

   

    while(T--!=0){

   

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

   

    int n=Integer.parseInt(str[0]);

    int m=Integer.parseInt(str[1]);

   

    Node bitmap[][]=new Node[n][m];

   

    int sol[][]=new int[n][m];

    String temp;

    Node temp2;

    int c=1;

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

    temp=br.readLine();

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

    temp2=new Node();

    temp2.x=i;

    temp2.y=j;

    temp2.value=Integer.parseInt(temp.charAt(j)+"");

    bitmap[i][j]=temp2;

    sol[i][j]=-1;

    }

    }

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

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

    if(bitmap[i][j].value==1){

    sol[i][j]=0;

    bfs(bitmap,bitmap[i][j],sol);

    }

    }

    }

    StringBuilder sb=new StringBuilder();

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

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

    //System.out.print(sol[i][j]+" ");

    sb.append(sol[i][j]+" ");;

    }

    //System.out.println();

    sb.append("\n");

    }

    System.out.print(sb);

    br.readLine();

   

    }

   

    }

    

    

    public static void bfs(Node bitmap[][],Node root,int sol[][]){

   

    int visited[][]=new int[bitmap.length][bitmap[0].length];

    Queue<Node> Q=new LinkedList<Node>();

    Q.offer(root);

   

    visited[root.x][root.y]=1;

    Node temp;

    int x1,y1,d;

    while(!Q.isEmpty()){

    temp=Q.poll();

    x1=temp.x;y1=temp.y;

   

    if(x1-1>=0&&visited[x1-1][y1]==0&&bitmap[x1-1][y1].value!=1){

    Q.offer(bitmap[x1-1][y1]);

    visited[x1-1][y1]=1;

    d=(int)Math.abs((x1-1)-root.x)+(int)Math.abs(y1-root.y);

    if(sol[x1-1][y1]==-1){

    sol[x1-1][y1]=d;

    }else{

    sol[x1-1][y1]=Math.min(sol[x1-1][y1],d);

    if(sol[x1-1][y1]<d){

    Q.remove(bitmap[x1-1][y1]);

    }

    }

    }

    if(y1-1>=0&&visited[x1][y1-1]==0&&bitmap[x1][y1-1].value!=1){

    Q.offer(bitmap[x1][y1-1]);

    visited[x1][y1-1]=1;

    d=(int)Math.abs(x1-root.x)+(int)Math.abs((y1-1)-root.y);

    if(sol[x1][y1-1]==-1){

    sol[x1][y1-1]=d;

    }else{

    sol[x1][y1-1]=Math.min(sol[x1][y1-1],d);

    if(sol[x1][y1-1]<d){

    Q.remove(bitmap[x1][y1-1]);

    }

    }

    }

    if(y1+1<bitmap[0].length&&visited[x1][y1+1]==0&&bitmap[x1][y1+1].value!=1){

    Q.offer(bitmap[x1][y1+1]);

    visited[x1][y1+1]=1;

    d=(int)Math.abs(x1-root.x)+(int)Math.abs((y1+1)-root.y);

    if(sol[x1][y1+1]==-1){

    sol[x1][y1+1]=d;

    }else{

    sol[x1][y1+1]=Math.min(sol[x1][y1+1],d);

    if(sol[x1][y1+1]<d){

    Q.remove(bitmap[x1][y1+1]);

    }

    }

    }

    if(x1+1<bitmap.length&&visited[x1+1][y1]==0&&bitmap[x1+1][y1].value!=1){

    Q.offer(bitmap[x1+1][y1]);

    visited[x1+1][y1]=1;

    d=(int)Math.abs((x1+1)-root.x)+(int)Math.abs(y1-root.y);

    if(sol[x1+1][y1]==-1){

    sol[x1+1][y1]=d;

    }else{

    sol[x1+1][y1]=Math.min(sol[x1+1][y1],d);

    if(sol[x1+1][y1]<d){

    Q.remove(bitmap[x1+1][y1]);

    }

    }

    }

    }

   

   

   

    }

    

    

    

}

Input:-

1
3 4
0001
0011
0110

Output:-

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

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

Spoj-PARTY - Party Schedule Java Solution

Problem Statement:-http://www.spoj.com/problems/PARTY/

Explanation:

This problem can be easily sovled by Dynamic Programming Approach.This problem can be solved  by two methods i.e. recursive approach and iterative approach.Here, an iterative approach is given.The key point to solve problem is that which party is to be selected or not and to maximize the fun and cost should be in budget.

The first example case data maintained is given i.e.

5 3

1 60

2 100

3 120

Data maintained for this case:

     0     1     2      3      4       5

0   0     0     0      0      0       0

1   0    60    60    60    60     60

2   0    60    100  160  160   160

3   0    60    100  120  180   220

Program:

/**

 * @(#)PARTY.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/12/20

 */

import java.io.*;

class PARTY {

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

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

   

    while(true){

   

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

   

    int budget=Integer.parseInt(temp[0]);

    int n=Integer.parseInt(temp[1]);

   

    if(budget==0&&n==0){

    break;

    }

   

    int ar[][]=new int[n+1][budget+1];

   

    int cost[]=new int[n];

    int val[]=new int[n];

   

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

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

    cost[i]=Integer.parseInt(temp[0]);

    val[i]=Integer.parseInt(temp[1]);

    }

   

    for(int i=0;i<n+1;i++){

    for(int b=0;b<budget+1;b++){

   

    if(i==0||b==0){

    ar[i][b]=0;

    }else if(cost[i-1]<=b){

    ar[i][b]=Math.max(val[i-1]+ar[i-1][b-cost[i-1]],ar[i-1][b]);

    }else{

    ar[i][b]=ar[i-1][b];

    }

   

    }

    }

    int i=n,b=budget;

    while(ar[i][b]==ar[i][b-1]){

    b--;

    }

   

   

    System.out.println(b+" "+ar[n][budget]);//find(budget,cost,val,n-1));

   

   

    br.readLine();

    }

   

    }

    

}

Sample Input:

5 3

1 60

2 100

3 120

50 10

12 3

15 8

16 9

16 6

10 2

21 9

18 4

12 4

17 8

18 9 

50 10

13 8

19 10

16 8

12 9

10 2

12 8

13 5

15 5

11 7

16 2

0 0

Sample Output:

5 220

49 26

48 32

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