[hackerrank] Ema's Supercomputer(c++)

www.hackerrank.com/challenges/two-pluses/problem

Ema's Supercomputer | HackerRank

 

 

풀이과정

1. 주어진 그리드 맵에서 그림과 같이 크로스를 2개 그려서 두 크로스의 곱의 최댓값을 구하는 문제이다.

 

2. BFS를 이용하여 크로스를 그려주었다. 4방향 모두 이동 할 수 있는지 체크를 하고, 한 방향이라도 갈 수 없다면 취소하고 리턴 시켰다.

 

3. 모든 경우의 수를 체크해줘야 한다. 

 

 

* 현재 위치에서 최대로 9칸 크로스를 그릴 수 있어도, 5칸 크로스의 경우도 따지고 들어가야한다. (곱의 최댓값이다.)

 

소스코드

int dx[4] = {1, -1 ,0 ,0};
int dy[4] = {0, 0, 1, -1};
int visited[15][15] = {0,};
int MAX_ROW;
int MAX_COL;
int answer = 0;
vector<pair<int, int>> info;
bool bfs(int y, int x, vector<string> grid, int maxArea)  {
    visited[y][x] = 1;
    if (maxArea == 1) {
        return true;
    }
    int area = 1;
    vector<pair<int, int>> v;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= MAX_COL || ny >= MAX_ROW || grid[ny][nx] == 'B' || visited[ny][nx] == 1) {
            return false;
        }
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        v.push_back(make_pair(nx, ny));
        visited[ny][nx] = 1;
        area++;
    }

    while(1) {
        if (area == maxArea) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            pair<int, int> cur = v[i];
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || ny < 0 || nx >= MAX_COL || ny >= MAX_ROW || grid[ny][nx] == 'B' || visited[ny][nx] == 1) {
                return false;
            }
        }
        for (int i = 0; i < 4; i++) {
            pair<int, int> cur = v[i];
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            visited[ny][nx] = 1;
            v[i].first = nx;
            v[i].second = ny;
            area++;
        }
    }
}
void solve(int depth, int cur, vector<string> grid, int sum) {
    if (depth == 2) {
        if (sum > answer) {
            answer = sum;
        }
        return;
    }
    int _visited[15][15] = {0,};
    memcpy(_visited, visited, sizeof(visited));
    for (int i = cur; i < info.size(); i++) {
        if (visited[info[i].second][info[i].first] == 0) {
            int _area = 1;
            while(bfs(info[i].second, info[i].first, grid, _area)) {
                solve(depth + 1, i + 1, grid, sum * _area);
                memcpy(visited, _visited, sizeof(visited));
                _area+=4;
            }
            memcpy(visited, _visited, sizeof(visited));
        }
    }
}

int twoPluses(vector<string> grid) {

    MAX_ROW = grid.size();
    MAX_COL = grid[0].size();
    for (int i = 0; i < MAX_ROW; i++) {
        for (int j = 0; j < MAX_COL; j++) {
            if (grid[i][j] == 'G') {
                info.push_back(make_pair(j, i));
            }
        }
    }
    if (info.size() <= 1) {
        return 0;
    }
    solve(0, 0, grid, 1);
    return answer;
}