домино

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<cmath>
#define all(container) container.begin(), container.end()
#define fors(counter, start, finish) for (ll counter = start; counter < finish; ++counter)
#define forb(counter, start, finish) for (int counter = start; counter >= finish; --counter)
#define vec(type) std::vector<type>
#define dvec(type) std::vector<std::vector<type>>
#define cout(val) std::cout << val << std::endl;
#define ll int64_t
//#define fin std::cin

ll size, w, h;
int ans = 1000;
std::map<char, std::pair<std::pair<int, int>, std::pair<int, int>>> lit;

std::map<char, bool> done;
vec(int) di = { 0, 0, -1, 1 };
vec(int) dj = { -1, 1, 0, 0 };

int check(dvec(bool)& pol) {
    int res = 0;
    fors(i, 0, w) {
        fors(j, 0, h) {
            fors(q, 0, 4) {
                i += di[q]; j += dj[q];
                if (i >= 0 && j >= 0 && i < w && j < h) {
                    if (pol[i - di[q]][j - dj[q]] == pol[i][j]) {
                        res++;
                    }
                }
                i -= di[q]; j -= dj[q];
            }
        }
    }
    return res;
}

dvec(bool) rec(dvec(bool)& pol, dvec(bool)& res) {
    bool f = false;
    for (auto& i : lit) {
        if (done[i.first]) {
            f = true;
            done[i.first] = false;
            pol[i.second.first.first][i.second.first.second] = true;
            pol[i.second.second.first][i.second.second.second] = false;
            rec(pol, res);
            pol[i.second.first.first][i.second.first.second] = false;
            pol[i.second.second.first][i.second.second.second] = true;
            rec(pol, res);
            done[i.first] = true;
        }
    }
    int temp = check(pol);
    if (!f && ans > temp) {
        res = pol;
        ans = temp;
    }
    return res;
}

int main() {
    std::ifstream fin("input.txt");
    //std::ofstream fout("output.txt");
    fin >> w >> h;
    size = w * h / 2;
    dvec(char) dom(w, vec(char) (h));
    dvec(bool) pol(w, vec(bool) (h));
    dvec(bool) res(w, vec(bool) (h));
    fors(i, 0, w) {
        fors(j, 0, h) {
            fin >> dom[i][j];
            if (lit[dom[i][j]].first.first == 0) {
                lit[dom[i][j]].first.first = i + 1;
                lit[dom[i][j]].first.second = j + 1;
                done[dom[i][j]] = true;
            }
            else {
                lit[dom[i][j]].first.first--;
                lit[dom[i][j]].first.second--;
                lit[dom[i][j]].second.first = i;
                lit[dom[i][j]].second.second = j;
                done[dom[i][j]] = true;
            }
        }
    }

    res = rec(pol, res);

    fors(i, 0, w) {
        fors(j, 0, h)
            std::cout << (res[i][j] == 0 ? '-' : '+');
        std::cout << std::endl;
    }
    return 0;
}