fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int a[110][110];
  6. int dp[110][110];
  7. int crack[110][110];
  8. int main()
  9. {
  10.     int t;
  11.         scanf("%d",&t);
  12.  
  13.         while(t--)
  14.         {
  15.         memset(a,0,sizeof(a));
  16.         memset(crack,0,sizeof(crack));
  17.         memset(dp,0,sizeof(dp));
  18.                 int n,m;
  19.                 scanf("%d%d",&n,&m);
  20.                 char s[110];
  21.  
  22.                 for(int i=0;i<n;i++)
  23.                 {
  24.                         scanf("%s",s);
  25.                         for(int j=0;j<m;j++)
  26.                         {
  27.                                 a[i][j]=s[j]-'0';
  28.  
  29.                         }
  30.  
  31.                 }
  32.                 dp[0][0]=a[0][0]+a[0][1]+a[1][0];
  33.                 for(int i=1;i<m;i++)
  34.                 {
  35.                         dp[0][i]=dp[0][i-1]+a[1][i]+a[0][i+1];
  36.                 }
  37.                 for(int i=1;i<n;i++)
  38.                 {
  39.                         dp[i][0]=dp[i-1][0]+a[i][1]+a[i+1][0];
  40.                         crack[i][0]=1;
  41.                 }
  42.                 for(int i=1;i<n;i++)
  43.                 {
  44.                         for(int j=1;j<m;j++)
  45.                         {
  46.                                 int left,up;
  47.                                 left=dp[i][j-1];
  48.                                 if(crack[i][j-1]==2)
  49.                                 left+=a[i-1][j];
  50.  
  51.                                 up=dp[i-1][j];
  52.                                 if(crack[i-1][j]==1)
  53.                                 up+=a[i][j-1];
  54.                                 int ans=left;
  55.                                 if(left>up)
  56.                                 {
  57.                                         ans=up;
  58.                                         crack[i][j]=1;
  59.  
  60.                                 }
  61.                                 else if(left<up)
  62.                                 {
  63.                                         ans=left;
  64.                                         crack[i][j]=2;
  65.                                 }
  66.                                 dp[i][j]=ans+a[i+1][j]+a[i][j+1];
  67.  
  68.                         }
  69.                 }
  70.  
  71.                 cout<<dp[n-1][m-1]<<endl;
  72.         }
  73.         return 0;
  74. }
Success #stdin #stdout 0s 2996KB
comments (?)
stdin
copy 
1
10 7
0010111
1100000
0010011
0111011
0110001
1001011
0101000
0110101
1011011
1100001
stdout
copy 
13
https://ideone.com/7O2hp9
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!