LeetCode Biweekly Contest 3
問題文
省略
省略
#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)