fork download
copy 
  1. #include<stdio.h>
  2.  
  3. int findmin(int (*arr)[51],int rlow,int rhigh, int clow, int chigh)
  4. {
  5.     if(rlow==rhigh||clow==chigh)
  6.     return 0;
  7.     int i,min,p=0,q=0,r=0,s=0;
  8.     for(i=clow;i<chigh;i++)
  9.        p=p+arr[rlow][i];
  10.        for(i=clow;i<chigh;i++)
  11.        q=q+arr[rhigh-1][i];
  12.        for(i=rlow;i<rhigh;i++)
  13.        r=r+arr[i][clow];
  14.        for(i=rlow;i<rhigh;i++)
  15.        s=s+arr[i][chigh-1];
  16.  
  17.        min=p;
  18.        if(q<min)
  19.        min=q;
  20.        if(r<min)
  21.        min=r;
  22.        if(s<min)
  23.        min=s;
  24.  
  25.        return(min);
  26. }
  27.  
  28. int deletearr(int (*arr)[51],int rlow,int rhigh,int clow,int chigh,int a,int b,int atotal, int btotal)
  29. {
  30.    if(clow==chigh||rlow==rhigh)
  31.    {
  32.       if(atotal>btotal)
  33.       return (atotal);
  34.       else if(btotal>atotal)
  35.       return(btotal);
  36.       else
  37.       return(atotal+btotal);
  38.    }
  39.    int p=0,q=0,r=0,s=0,i,min,max,temp,count,value;
  40.    char MAX;
  41.    if(a==1)
  42.    {
  43.        for(i=clow;i<chigh;i++)
  44.        p=p+arr[rlow][i];
  45.        for(i=clow;i<chigh;i++)
  46.        q=q+arr[rhigh-1][i];
  47.        for(i=rlow;i<rhigh;i++)
  48.        r=r+arr[i][clow];
  49.        for(i=rlow;i<rhigh;i++)
  50.        s=s+arr[i][chigh-1];
  51.  
  52.        min=p;
  53.        if(q<min)
  54.        min=q;
  55.        if(r<min)
  56.        min=r;
  57.        if(s<min)
  58.        min=s;
  59.  
  60.        if(min==p)
  61.        rlow=rlow+1;
  62.        else if(min==q)
  63.        rhigh=rhigh-1;
  64.        else if(min==r)
  65.        clow=clow+1;
  66.        else
  67.        chigh=chigh-1;
  68.  
  69.        deletearr(arr,rlow,rhigh,clow,chigh,0,1,atotal+min,btotal);
  70.  
  71.    }
  72.    else
  73.    {
  74.        for(i=clow;i<chigh;i++)
  75.        p=p+arr[rlow][i];
  76.        for(i=clow;i<chigh;i++)
  77.        q=q+arr[rhigh-1][i];
  78.        for(i=rlow;i<rhigh;i++)
  79.        r=r+arr[i][clow];
  80.        for(i=rlow;i<rhigh;i++)
  81.        s=s+arr[i][chigh-1];
  82.  
  83.        max=p;
  84.        if(q>=max)
  85.        max=q;
  86.        if(r>=max)
  87.        max=r;
  88.        if(s>=max)
  89.        max=s;
  90.  
  91.        count=0;
  92.        if(max==p)
  93.        {
  94.            temp=findmin(arr,rlow+1,rhigh,clow,chigh);
  95.            min=temp;MAX='p';count++;
  96.        }
  97.        if(max==q)
  98.        {
  99.            temp=findmin(arr,rlow,rhigh-1,clow,chigh);
  100.            if(count==0)
  101.            {min=temp;MAX='q';count++;}
  102.            else if(temp<min)
  103.            {min=temp;MAX='q';}
  104.        }
  105.        if(max==r)
  106.        {
  107.           temp=findmin(arr,rlow,rhigh,clow+1,chigh);
  108.            if(count==0)
  109.            {min=temp;MAX='r';}
  110.            else if(temp<min)
  111.            {min=temp;MAX='r';} 
  112.        }
  113.        if(max==s)
  114.        {
  115.            temp=findmin(arr,rlow,rhigh,clow,chigh-1);
  116.            if(count==0)
  117.            {min=temp;MAX='s';}
  118.            else if(temp<min)
  119.            {min=temp;MAX='s';}
  120.        }
  121.  
  122.        if(MAX=='p')
  123.        {rlow=rlow+1;value=p;}
  124.        else if(MAX=='q')
  125.        {rhigh=rhigh-1;value=q;}
  126.        else if(MAX=='r')
  127.        {clow=clow+1;value=r;}
  128.        else if(MAX=='s')
  129.        {chigh=chigh-1;value=s;}
  130.  
  131.        deletearr(arr,rlow,rhigh,clow,chigh,1,0,atotal,btotal+value);
  132.  
  133.    }
  134. }
  135.  
  136. int main()
  137. {
  138.    int t,i,j,k,r,c,arr[51][51],res;
  139.    scanf("%d",&t);
  140.    for(i=0;i<t;i++)
  141.    {
  142.       scanf("%d%d",&r,&c);
  143.       for(j=0;j<r;j++)
  144.       for(k=0;k<c;k++)
  145.       scanf("%d",&arr[j][k]);
  146.  
  147.       res=deletearr(arr,0,r,0,c,1,0,0,0);
  148.       printf("%d\n",res);
  149.    }
  150. }
Success #stdin #stdout 0.01s 2684KB
comments (?)
stdin
copy 
1
2 2 
0 1000000000
1 1000000000
stdout
copy 
2000000000
https://ideone.com/anGLHs
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

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!