最大正方形を検索(Lv 2)



この問題はできなかった
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を作るのがコア