[TYVJ]P 1027パパイヤ畑

パパイヤ畑
 
バックグラウンドBackground
USACO OCT09 4TH
 
Descriptionの説明
BessieはうっかりFarmer Johnの畑をぶらぶらして、隣の農民の畑に入った.彼女はパパイヤを持ち上げて
瓜は乳牛にとっておいしいものではない.このパパイヤ林は一般的なウィスコンシン州の畑のように一つに分割されています
R行C列のメッシュ(1<=R<=40,1<=C<=40).Bessieは1つの格子からX軸または
Y軸が平行な直線が隣接する令一格まで行きます.Bessieは最初、彼女自身がパパイヤ林にいたことに気づいた(1,1)、つまり第
一行の第一列はゆっくりとパパイヤを噛んでいる.
Bessieはいつも彼女が最も信頼している双眼鏡で隣接する格の低いキュウリの数を数えている.そして彼女は泳ぎました
最も多く食べられていないパパイヤの隣接する格子(この洋の格子が一つしかないことを保証する)までぶらぶらします.
この移動方法によって、最終的にBessieはいつも(R,C)で止まってそこのパパイヤを食べます.
このパパイヤ林の大きさと各格のパパイヤ数F_を与えるij(1<=F_ij<=100)は、Bessieに全部食べさせていただきました
パパイヤはいくつですか.
 
入力形式InputFormat
*1行目:2つのスペースで区切られた整数RとC.
*2行目からR+1行目:i+1行目はC個のスペースで区切られた整数で、i行目の各格の果物数を表す.つまりF_i1, 
F_i2, ..., F_iC.
 
出力フォーマットOutputFormat
*1行目:単独の整数で、Bessieが右下(R,C)のパパイヤを食べ終わって牛舎に戻るまで、
全部でパパイヤ林でパパイヤを何個食べましたか.
 
サンプル入力SampleInput[データのコピー]
3 43 3 4 54 5 3 21 7 4 2
 
サンプル出力SampleOutput[データのコピー]
39
 
データ範囲とコメントHint
Bessieは下図の数字の横のアルファベットの順にパパイヤを食べます.
     (1,1) ---> (1,C)
(1,1) 3a  3   4g  5h  (1,C)
  |   4b  5c  3f  2i    |
(R,1) 1   7d  4e  2j  (R,C)
     (R,1) ---> (R,C)
彼女はパパイヤ39個を食べ、残り4個は食べなかった(つまり2個を除いて難を免れ、残りの格子はBessieに掃かれた
ぶらぶらした).
 
問題:

#include <stdbool.h>

#include <stdio.h>

int main(void)

{

    int i,j,r,c,a[41][41],xi=1,yi=1,maxx=1,maxy=1,max;

    bool b[41][41]={false};

    long sum=0;

    scanf("%d%d
",&r,&c);

    for (i=1;i<=r;i++)

    { 

        for (j=1;j<=c;j++)

        {

         scanf("%d",&a[i][j]);

         b[i][j]=true;

        }

     }

   

            

   sum=sum+a[1][1];

     b[1][1]=false;

    while (true)

    {

        

        max=-1;

        if ((b[xi][yi+1]==true)&&(a[xi][yi+1]>max))

        {

            maxx=xi;maxy=yi+1;

            max=a[xi][yi+1];

        }

         if ((b[xi][yi-1]==true)&&(a[xi][yi-1]>max))

        {

            maxx=xi;maxy=yi-1;

            max=a[xi][yi-1];

        }

          if ((b[xi+1][yi]==true)&&(a[xi+1][yi]>max))

        {

            maxx=xi+1;maxy=yi;

            max=a[xi+1][yi];

        }

           if ((b[xi-1][yi]==true)&&(a[xi-1][yi]>max))

        {

            maxx=xi-1;maxy=yi;

            max=a[xi-1][yi];

        }

           b[maxx][maxy]=false;

           sum=sum+a[maxx][maxy];

           xi=maxx;yi=maxy;

           if ((maxx==r)&&(maxy==c)) break;

            

    }

    

printf("%d
",sum);

return 0;

        

        

}