最大正方形を検索(Lv 2)
1504 ワード
この問題はできなかった
DPの場合、前の段階が後の段階に影響し、点火式の場合に使用できます.
#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> board)
{
int answer = board[0][0];
int iTemp;
for(int i=1; i<board.size(); i++)
{
for(int j=1; j<board[0].size(); j++)
{
if(board[i][j]!=0)
{
board[i][j] = min(board[i][j-1], board[i-1][j]);
board[i][j] = min(board[i][j], board[i-1][j-1])+1;
answer = max(answer, board[i][j]);
}
}
}
return answer*answer;
}
answer = 0; やると1の場合caseが出てくるので[0][0]する必要があります.[点火関係]
board[i][j] = min(board[i][j-1], board[i-1][j]);
board[i][j] = min(board[i][j], board[i-1][j-1])+1;
3方向に最小の+1を作るのがコア
Reference
この問題について(最大正方形を検索(Lv 2)), 我々は、より多くの情報をここで見つけました https://velog.io/@imalive77/가장-큰-정사각형-찾기Lv2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol