Tuesday, January 6, 2015

Topcoder srm 637 div2 500 problem

How I approach this problem is finding shortest path

and total path minus # path count minus short path minus will be a answer


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package srm637;

public class PathGameDiv2 {
 public static void main(String args[]){
  PathGameDiv2 pg = new PathGameDiv2();
  String[] board = {"....#.##.....#..........." 
       ,"..#......#.......#..#...."};
  
  System.out.println(pg.calc(board));
 }
 
 public int calc(String[] board){
  
  int len = board[0].length();
   
  
  int total =0;
  int p =0;
  
  total = Math.min(pathSum(p, len, board), pathSum(p+1, len, board));
  
  int minus =0;
  
  for(int i=0; i<board.length; i++){
   for(int j=0; j<board[i].length(); j++){
    if(board[i].charAt(j) == '#'){
     minus ++;
    }
   }
  }
  
  return (board[0].length()* 2) - total - minus;
 }
 
 public int pathSum(int p, int len, String[] board){
  int total =0;
  for(int i=0; i<len; i++){
   if(board[p].charAt(i) =='.'){
    total ++;
   }else{
    if(p==0){
     p=1;
     i= i-2;
    }else{
     p=0;
     i = i-2;
    }
   }
  } 
  return total;
 }
}

No comments:

Post a Comment