3967번

3967번 - 매직 스타

백트래킹 문제로 사용하지 않은 알파벳을 A부터 L까지 전부 사용하면서 문제를 풀었다.

6곳을 모두 체크해야하는데, 그냥 이차원 배열로 체크하도록 선언을 미리 했다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
char map[5][9];
int dx[6][4] = { {1,1,1,1},{3,3,3,3},{0,1,2,3},{0,1,2,3},{1,2,3,4},{1,2,3,4} };
int dy[6][4] = { {1,3,5,7},{1,3,5,7},{4,3,2,1},{4,5,6,7},{1,2,3,4},{7,6,5,4} };
bool used[12];
char op[12];
vector<pair<int, int>> q;
void go(int k,int goal)
{
    if (k == goal)
    {
        for (int i = 0; i < 6; i++)
        {
            int sum = 0;
            for (int j = 0; j < 4; j++)
            {
                int x = dx[i][j];
                int y = dy[i][j];
                sum += map[x][y] - 'A' + 1;
            }
 
            if (sum != 26)
            {
                return;
            }
        }
 
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                cout << map[i][j];
            }
            cout << "\n";
        }
        exit(1);
    }
 
    
 
    
    for (int i = 0; i < 12; i++)
    {
        if (!used[i])
        {
            used[i] = true;
            map[q[k].first][q[k].second] = i+'A';
            go(k + 1, goal);
            used[i] = false;
            
        }
    }
    
 
}
int main()
{
    
    //freopen("input.txt", "r", stdin);
 
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> map[i][j];
            if (map[i][j] >= 'A' && map[i][j] <= 'Z')
            {
                used[map[i][j] - 'A'] = true;
            }
 
            if (map[i][j] == 'x')
            {
                q.push_back({ i,j });
            }
        }
    }
 
    go(0,q.size());
 
 
    return 0;
}