[LeetCode] 764. Largest Plus Sign

https://leetcode.com/problems/largest-plus-sign/

Largest Plus Sign - LeetCode

Largest Plus Sign - Medium

 

1과 0으로 map이 주어졌을때, 플러스 모양의 최대 크기를 구하는 문제다.

map크기만큼 또다른 map을 만들고, int pair를 저장해주자.

(0,0) 에서 (n-1, n-1)까지 훑으며 pair의 한쪽에는 바로 윗쪽이 1이상이고 해당셀도 1이상이라면 윗쪽 +1로 저장해주고,

다른쪽은 윗쪽대신 왼쪽으로 하여 똑같이 해준다.

이러면 위와 왼쪽에서 이어지는 플러스의 변의 길이가 저장된다.

 

이번엔 반대로 (n-1, n-1)에서 (0,0)으로 훑어주며 윗쪽대신 아래쪽으로, 왼쪽대신 오른쪽으로 바꿔 진행해준다.

그리고 각각마다 위에서 온것, 왼쪽에서 온것, 아래에서 온것, 오른쪽에서 온것의 변의 길이 중 최소값을 ret과 비교하여 ret을 갱신해주자.

 

전체 풀이 코드

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<pair<int,int>>> m(n, vector<pair<int,int>>(n,make_pair(1,1)));
        int ret=0;
        for (auto mine:mines) m[mine[0]][mine[1]] = make_pair(0,0);
        for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
            if (i && m[i-1][j].first && m[i][j].first) m[i][j].first = m[i-1][j].first+1;
            if (j && m[i][j-1].second && m[i][j].second) m[i][j].second = m[i][j-1].second+1;
        }
        for (int i=n-1; i>-1; i--) for (int j=n-1; j>-1; j--) {
            int temp = min(m[i][j].first, m[i][j].second);
            if (i<n-1 && m[i+1][j].first && m[i][j].first) m[i][j].first = m[i+1][j].first + 1;
            else m[i][j].first = m[i][j].first?1:0;
            if (j<n-1 && m[i][j+1].second && m[i][j].second) m[i][j].second = m[i][j+1].second + 1;
            else m[i][j].second = m[i][j].second?1:0;
            ret = max(ret, min(m[i][j].first,min(temp,m[i][j].second)));
        }
        return ret;
    }
};