Aizu Online Judge 0203 A New Plan of Aizu Ski Resort

■0203 A New Plan of Aizu Ski Resort

dp[j][i]=(i,j)に到達するまでの滑り方のパターン数
としてDP．
dp[0][i]=
0 - (i,0)に障害物がある
1 - (i,0)に障害物がない
あとは，説明通りに更新していく．dp[n]まで用意しておいて，dp[n-1]とdp[n]の総和が答え．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int m, n;  
17.  int[][] a;  
18.   
19.  void run(){  
20.   for(;;){  
21.    m=sc.nextInt();  
22.    n=sc.nextInt();  
23.    if((m|n)==0){  
24.     break;  
25.    }  
26.    a=new int[n][m];  
27.    for(int j=0; j<n; j++){  
28.     for(int i=0; i<m; i++){  
29.      a[j][i]=sc.nextInt();  
30.     }  
31.    }  
32.    solve();  
33.   }  
34.  }  
35.   
36.  void solve(){  
37.   long[][] dp=new long[n+1][m];  
38.   for(int i=0; i<m; i++){  
39.    if(a[0][i]==0){  
40.     dp[0][i]=1;  
41.    }  
42.   }  
43.   for(int j=0; j<n-1; j++){  
44.    for(int i=0; i<m; i++){  
45.     switch(a[j][i]){  
46.     case 0:  
47.      if(i-1>=0&&a[j+1][i-1]==0)  
48.       dp[j+1][i-1]+=dp[j][i];  
49.      if(a[j+1][i]!=1)  
50.       dp[j+1][i]+=dp[j][i];  
51.      if(i+1<m&&a[j+1][i+1]==0)  
52.       dp[j+1][i+1]+=dp[j][i];  
53.      break;  
54.     case 2:  
55.      if(j>=n-2||a[j+2][i]!=1)  
56.       dp[j+2][i]+=dp[j][i];  
57.      break;  
58.     }  
59.    }  
60.   }  
61.   long ans=0;  
62.   for(int j=n-1; j<n+1; j++){  
63.    for(int i=0; i<m; i++){  
64.     ans+=dp[j][i];  
65.    }  
66.   }  
67.   println(ans+"");  
68.  }  
69.   
70.  void debug(Object... os){  
71.   System.err.println(Arrays.deepToString(os));  
72.  }  
73.   
74.  void print(String s){  
75.   System.out.print(s);  
76.  }  
77.   
78.  void println(String s){  
79.   System.out.println(s);  
80.  }  
81.   
82.  public static void main(String[] args){  
83.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
84.   new Main().run();  
85.  }  
86. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[][] a;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  long[][] dp=new long[n+1][m];
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    dp[0][i]=1;
   }
  }
  for(int j=0; j<n-1; j++){
   for(int i=0; i<m; i++){
    switch(a[j][i]){
    case 0:
     if(i-1>=0&&a[j+1][i-1]==0)
      dp[j+1][i-1]+=dp[j][i];
     if(a[j+1][i]!=1)
      dp[j+1][i]+=dp[j][i];
     if(i+1<m&&a[j+1][i+1]==0)
      dp[j+1][i+1]+=dp[j][i];
     break;
    case 2:
     if(j>=n-2||a[j+2][i]!=1)
      dp[j+2][i]+=dp[j][i];
     break;
    }
   }
  }
  long ans=0;
  for(int j=n-1; j<n+1; j++){
   for(int i=0; i<m; i++){
    ans+=dp[j][i];
   }
  }
  println(ans+"");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}