3967번 매직 스타

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

82 ~ 92번 째 코드가 은근히 백트래킹에 많이 쓰인다.

vector의 인덱스로 백트래킹 함수의 인수로 쓰이는 것을 잊어버리면 안 된다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int Map[7][11];
 
bool use[100] = { false, }, stop = false;
 
vector<pair<int, int> > v;
 
bool check()
{
    int one = Map[1][1] + Map[1][3] + Map[1][5] + Map[1][7];
 
    int two = Map[1][1] + Map[2][2] + Map[3][3] + Map[4][4];
 
    if (one != two) return false;
 
    int three = Map[4][4] + Map[3][5] + Map[2][6] + Map[1][7];
 
    if (two != three) return false;
 
    int four = Map[0][4] + Map[1][3] + Map[2][2] + Map[3][1];
 
    if (three != four) return false;
 
    int five = Map[3][1] + Map[3][3] + Map[3][5] + Map[3][7];
 
    if (four != five) return false;
 
    int six = Map[3][7] + Map[2][6] + Map[1][5] + Map[0][4];
    
    if (five != six) return false;
 
    return true;
}
 
void simulation(int pos)
{
    if (stop) return;
 
    if (pos == v.size())
    {
        if (check())
        {
            for (int i = 0; i < 5; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (Map[i][j] == 0) printf(".");
 
                    if (1 <= Map[i][j] && Map[i][j] <= 12)
                    {
                        printf("%c", (char)(Map[i][j] + 'A' - 1));
                    }
                }
 
                printf("\n");
            }
 
            stop = true;
        }
 
        return;
    }
 
    for (int i = 1; i <= 12; i++)
        if (!use[i])
        {
            use[i] = true;
            Map[v.at(pos).first][v.at(pos).second] = i;
 
            simulation(pos + 1);
 
            use[i] = false;
            Map[v.at(pos).first][v.at(pos).second] = 0;        
        }
}
 
int main(void)
{
    char c;
 
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 9; j++)
        {
            cin >> c;
 
            if (c == '.' || c == 'x')
            {
                Map[i][j] = 0;
 
                if (c == 'x') v.push_back({ i, j });
 
                continue;
            }
 
            if ('A' <= c && c <= 'L')
            {
                Map[i][j] = c - 'A' + 1;
                use[c - 'A' + 1] = true;
            }
        }
 
    simulation(0);
 
    return 0;
}