ぷよぐやみんぐしたぽよ～☆

序論

　どうも。ぞでぃあっくです☆ハタチ♥大学生していますっ♥趣味は数学とぷよぐやみんぐ！情報科大学生なのですが、最近は数学のお勉強にハマっています！
　でもでも今回は、最近講義で出された課題について書かせて戴きたいと思っておりますぽよ～

本題

　講義で出た課題というのは、「引数をmとnとし、m×n行列の各マスにポイントを割り振る。右と下に各マスを移動できるものとし、通ったマスのポイントを加算していく。左上から右下まで移動したときの最大総ポイントを答えよ。」というものです。「宝集めゲーム」っていうらしい(？)fig.1 課題の例(4×5の場合)

　最初は全く分からなかったが、後々よく寝た(睡眠学習した)ことで、瞬殺できまちた☆思いのほか達成感があったので、これについて記事を書こうと思った次第です。

解答

　では、僕の考えたアルゴリズムを紹介しましょう。
　全探査を全ての経路の総和を算出して、最も大きな値を最大値として返すものとするならば、このアルゴリズムは全探査ではないです。方針としては、「各マスにそのマスにたどり着くまでの総和を割り当てる」という考えで解いていきます。そのような考えを念頭に置くと、まず、1行と1列の各マスの値は進行方向の制限性により一意的です。よって、まず値を入れちゃいましょう。(fig.2)

fig.2 1行と1列の各マスに値を割り振る

　他のマスは、上のようにはいかないですよね。まあでも、「各マスにそのマスにたどり着くまでの総和を割り当てる」という方針に変わりはないです。ここで大事なのは進行のパターンです。2×2の正方行列を考えたときに、右斜め下のマスに進むためには2パターンしかないということです。なので、その2パターンでどちらの方が大きいか比べ(fig.3)、大きい方をマスに割り振れば良いのです。(fig.4)

fig.3 2×2正方行列における進路

fig.4 2×2正方行列における最大地値を取る進路

　まあそこまで難しくないですね？どうですか？あとはこれを念頭に置いて、各マスに確実な値を端から順次に埋めていけばできますね。因みに、このfig.1のような場合は、39が最大値となるはずですがどうでしょうかね。(fig.5)

fig.5 プログラム実行例

　それと僕の書いたコードも載せちゃいます///

/*simauta.c*/
#include <stdio.h>

#define N 100

int main(){
  int i, j;
  int takara[N][N] = {{0}}; //各マスに価値を割り振るために用意
  int ship[N][N] = {{0}}; //ある位置での宝の価値の総和を表すために用意
  int south, east;

  /* 行数の入力 */
  printf("south = ");
  while(scanf("%d", &south)!= 1||south < 1||south > N){
    printf("Wrong number of rows.\n");
    printf("south = ");
    while(getchar() != '\n');
  }

  /* 列数の入力 */
  printf("east = ");
  while(scanf("%d", &east)!= 1||east < 1||east > N){
    printf("Wrong number of rows.\n");
    printf("east = ");
    while(getchar() != '\n');
  }

  /* 要素の入力 */
  for(i = 0;i <= south - 1;i++){
    printf("Please input number at matrix[%d][0~%d]: ", i, east - 1);
    for(j = 0;j <= east - 1;j++){
      while(scanf("%d", &takara[i][j])!=1){
        puts("incorrect input.");
        while(getchar() != '\n');
      }
    }
  }

  /* [0〜east][0]と[0][0〜south]まで進行したときの宝の価値の和 */
  for(i = 0;i <= south - 1;i++){
    if(i == 0) ship[i][0] = takara[0][0];
    else ship[i][0] += takara[i][0] + ship[i - 1][0];
  }
  for(i = 0;i <= east - 1;i++){
    if(i == 0) ship[0][i] = takara[0][0];
    else ship[0][i] += takara[0][i] + ship[0][i - 1];
  }

  /* れっつ航海☆ */
  for(i = 1;i <= south - 1;i++){
    for(j = 1;j <= east - 1;j++){
      ship[i][j] += takara[i][j] + ((ship[i - 1][j] >= ship[i][j - 1]) ? ship[i - 1][j] : ship[i][j - 1]);
      printf("ship[%d][%d] = %d\n", i, j, ship[i][j]);
    }
  }
  
  printf("Max = %d\n", ship[south - 1][east - 1]);
  return 0;
}

　まあ、再帰でも書けると思います。(#それはそう)
　どうも御覧いだだきましてありがとうございます(^^)またこういった記事を書いていきたいと思っておりますのでよろしくです！ではでは～