백준 17085번 십자가 2개 놓기 C++

https://www.acmicpc.net/problem/17085

17085번: 십자가 2개 놓기

 

백트래킹으로 십자가를 놓을 수 있는 좌표 2개를 찾고 거기서 설치할 수 있는 십자가의 곱의 최대값을 구하면 된다.

세가지 경우를 생각해서 그중 가장 큰 값을 구하였다.

1 : 좌표 1의 최대 십자가 크기를 구한 뒤 좌표 2의 최대 크기를 구한다.

2 : 좌표 2의 최대 십자가 크기를 구한 뒤 좌표 1의 최대 크기를 구한다.

3 : 좌표1, 좌표 2의 크기를 동시에 늘려가며 가능한 최대 크기를 구한다.

 

위의 세가지 경우중 가장 큰 값을 찾아주면서 문제를 해결하였다.

 

다 풀고보니 코드가 너무 난잡한 것 같다....

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

int n, m;
int ans = 0;
vector<vector<char>> board;

vector<int> idxes;
vector<bool> visited;

int CalculateVal1(int row1, int col1, int row2, int col2) {
    int cnt1 = 0;
    int cnt2 = 0;
    vector<vector<bool>> found(n, vector<bool>(m, false));
    found[row1][col1] = true;
    cnt1++;
    found[row2][col2] = true;
    cnt2++;
    int dist = 1;
    while (true) {
        bool possible = true;
        vector<pair<int, int>> tmp;
        for (int i = 0; i < 4; i++) {
            int nextRow = row1 + dRow[i] * dist;
            int nextCol = col1 + dCol[i] * dist;
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m) {
                possible = false;
                break;
            }
            if (board[nextRow][nextCol] == '.' || found[nextRow][nextCol]) {
                possible = false;
                break;
            }
            tmp.push_back({ nextRow,nextCol });
        }
        if (possible == false) break;
        for (auto a : tmp) {
            found[a.first][a.second] = true;
        }
        cnt1 += 4;
        dist++;
    }
    dist = 1;
    while (true) {
        bool possible = true;
        vector<pair<int, int>> tmp;
        for (int i = 0; i < 4; i++) {
            int nextRow = row2 + dRow[i] * dist;
            int nextCol = col2 + dCol[i] * dist;
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m) {
                possible = false;
                break;
            }
            if (board[nextRow][nextCol] == '.' || found[nextRow][nextCol]) {
                possible = false;
                break;
            }
            tmp.push_back({ nextRow,nextCol });
        }
        if (possible == false) break;
        for (auto a : tmp) {
            found[a.first][a.second] = true;
        }
        cnt2 += 4;
        dist++;
    }
    return cnt1 * cnt2;
}

int CalculateVal2(int row1, int col1, int row2, int col2) {
    int cnt1 = 0;
    int cnt2 = 0;
    vector<vector<bool>> found(n, vector<bool>(m, false));
    found[row1][col1] = true;
    cnt1++;
    found[row2][col2] = true;
    cnt2++;
    int dist = 1;
    while (true) {
        bool possible = true;
        vector<pair<int, int>> tmp;
        for (int i = 0; i < 4; i++) {
            int nextRow = row1 + dRow[i] * dist;
            int nextCol = col1 + dCol[i] * dist;
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m) {
                possible = false;
                break;
            }
            if (board[nextRow][nextCol] == '.' || found[nextRow][nextCol]) {
                possible = false;
                break;
            }
            tmp.push_back({ nextRow,nextCol });
        }
        if (possible == false) break;
        for (auto a : tmp) {
            found[a.first][a.second] = true;
        }
        cnt1 += 4;
        tmp.clear();
        for (int i = 0; i < 4; i++) {
            int nextRow = row2 + dRow[i] * dist;
            int nextCol = col2 + dCol[i] * dist;
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m) {
                possible = false;
                break;
            }
            if (board[nextRow][nextCol] == '.' || found[nextRow][nextCol]) {
                possible = false;
                break;
            }
            tmp.push_back({ nextRow,nextCol });
        }
        if (possible == false) break;
        for (auto a : tmp) {
            found[a.first][a.second] = true;
        }
        cnt2 += 4;
        dist++;
    }
    return cnt1 * cnt2;
}

void BT(int idx, int cnt) {
    int row = idx / m;
    int col = idx % m;
    if (cnt == 2) {
        int row1 = idxes[0] / m;
        int col1 = idxes[0] % m;
        int row2 = idxes[1] / m;
        int col2 = idxes[1] % m;
        
        int val1 = CalculateVal1(row1, col1, row2, col2);
        int val2 = CalculateVal1(row2, col2, row1, col1);
        int val3 = CalculateVal2(row1, col1, row2, col2);
        int maxVal = max(val1, max(val2, val3));
        //cout << row1 << " " << col1 << ", " << row2 << " " << col2 << " : " << maxVal << "\n";
        ans = max(ans, maxVal);
        return;
    }
    for (int i = idx; i < n * m; i++) {
        if (visited[i]) continue;
        if (board[i / m][i % m] == '.') continue;
        visited[i] = true;
        idxes.push_back(i);
        BT(i + 1, cnt + 1);
        visited[i] = false;
        idxes.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    board = vector<vector<char>>(n, vector<char>(m));
    visited = vector<bool>(n * m, false);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    BT(0, 0);
    cout << ans;
}