LeetCode Biweekly Contest 16 4問目 - Number of Paths with Max Score [1301]

Source

LeetCode Biweekly Contest 16
問題文

問題概要

省略

解法

省略

cLay（version 20200217-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

int X, Y, mx[100][100];
Modint cnt[100][100];

void ren(int &mx, Modint &cnt, int a, Modint b){
  if(mx < a) mx = a, cnt = 0;
  if(mx == a) cnt += b;
}

class Solution {
public:
  vector<int> pathsWithMaxScore(vector<string>& S) {
    X = S.size();
    Y = S[0].size();
    S[0][0] = '0';

    mx[X-1][Y-1] = 0;
    cnt[X-1][Y-1] = 1;
    rrep(i,X) rrep(j,Y){
      if(S[i][j]=='S') continue;
      if(S[i][j]=='X') mx[i][j] = -int_inf, cnt[i][j] = 0, continue;
      mx[i][j] = -int_inf;
      cnt[i][j] = 0;

      if(i+1 < X) ren(mx[i][j], cnt[i][j], mx[i+1][j]+S[i][j]-'0', cnt[i+1][j]);
      if(j+1 < Y) ren(mx[i][j], cnt[i][j], mx[i][j+1]+S[i][j]-'0', cnt[i][j+1]);
      if(i+1 < X && j+1 < Y) ren(mx[i][j], cnt[i][j], mx[i+1][j+1]+S[i][j]-'0', cnt[i+1][j+1]);
    }

    mx[0][0] >?= 0;
    return vector<int>{mx[0][0], (int)cnt[0][0]};
  }
};

Current time: 2024年04月24日21時05分54秒
Last modified: 2020年02月23日06時55分17秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)