LeetCode Biweekly Contest 3 4問目 - Path With Maximum Minimum Value [1102]

Source

LeetCode Biweekly Contest 3
問題文

問題概要

省略

解法

省略

cLayversion 20190630-1)のコード [C++に変換後]

#include<bits/stdc++.h>
using namespace std;
class Solution{
  public:
  int maximumMinimumPath(vector<vector<int>>& A){
    int KL2GvlyY, Lj4PdHRW, Q5VJL1cS, di[4]={-1,1,0,0}, dj[4]={0,0,-1,1}, i, j, k, ni, nj, ok[100][100], st[10000], sts, x, y;
    x = A.size();
    y = A[0].size();
    Lj4PdHRW = 0;
    KL2GvlyY = 1000000000;
    while(Lj4PdHRW < KL2GvlyY){
      if((Lj4PdHRW + KL2GvlyY)%2==0){
        Q5VJL1cS = (Lj4PdHRW + KL2GvlyY) / 2;
      }
      else{
        Q5VJL1cS = (Lj4PdHRW + KL2GvlyY + 1) / 2;
      }
      sts = 0;
      for(i=0;i<x;i++){
        for(j=0;j<y;j++){
          ok[i][j] = 0;
        }
      }
      if(A[0][0] >= Q5VJL1cS){
        st[sts++] = 0;
        ok[0][0] = 1;
      }
      while(sts){
        k = st[--sts];
        i = k / y;
        j = k % y;
        for(k=0;k<4;k++){
          ni = i + di[k];
          nj = j + dj[k];
          if(ni < 0 || nj < 0 || ni >= x || nj >= y){
            continue;
          }
          if(A[ni][nj] < Q5VJL1cS){
            continue;
          }
          if(ok[ni][nj]){
            continue;
          }
          ok[ni][nj] = 1;
          st[sts++] = ni*y+nj;
        }
      }
      if(ok[x-1][y-1]){
        Lj4PdHRW = Q5VJL1cS;
      }
      else{
        KL2GvlyY = Q5VJL1cS - 1;
      }
    }
    return KL2GvlyY;
  }
}
;
// cLay varsion 20190630-1

// --- original code ---
// class Solution {
// public:
//   int maximumMinimumPath(vector<vector<int>>& A) {
//     int i, j, k, ni, nj, di[4]={-1,1,0,0}, dj[4]={0,0,-1,1};
//     int x, y;
//     int ok[100][100];
//     int st[10000], sts;
//     x = A.size();
//     y = A[0].size();
// 
//     return bsearch_max[int,z,0,1d9][
//       sts = 0;
//       rep(i,x) rep(j,y) ok[i][j] = 0;
//       if(A[0][0] >= z) st[sts++] = 0, ok[0][0] = 1;
//       while(sts){
//         k = st[--sts];
//         i = k / y;
//         j = k % y;
//         rep(k,4){
//           ni = i + di[k];
//           nj = j + dj[k];
//           if(ni < 0 || nj < 0 || ni >= x || nj >= y) continue;
//           if(A[ni][nj] < z) continue;
//           if(ok[ni][nj]) continue;
//           ok[ni][nj] = 1;
//           st[sts++] = ni*y+nj;
//         }
//       }
//     ](ok[x-1][y-1]);
//   }
// };
// {
//   // main関数を適当に処理する
// }

Current time: 2024年03月28日17時27分31秒
Last modified: 2019年06月30日03時09分20秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)

ログイン: