Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <iomanip>
- #include <algorithm>
- #include <queue>
- #include <random>
- using namespace std;
- #define int long long
- #define pb push_back
- #define sqr(x) (x)*(x)
- #define IOS ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
- #define amas(a) for (auto&c:a) cout<<c<<" ";
- #define double long double
- int ma[10][10];
- int ans[10][10];
- int n, m, c;
- //int dp[3][10];//цвет.одинакового цвета в строке (уже выбранных)
- //int dp2[3][10];// одинакового цвета в столбце(уже выбранных)
- bool allf = false;
- void rec(int i, int j) {
- if (i == n) {
- for (int i1 = 0; i1 < n; i1++) {
- for (int j1 = 0; j1 < m; j1++) cout << ma[i1][j1] << " ";
- cout << "\n";
- }
- //char c;
- //cin >> c;
- //ans = ma;
- allf = true;
- }
- else {
- bool ex = true;
- int kus = 0;
- vector<int>ch(4);
- while (1) {
- if (kus == 3) break;
- int g = rand() % c + 1;
- while (ch[g]) {
- g = rand() % c + 1;
- }
- ch[g] = 1; kus++;
- // выбираем цвет
- bool f = true;
- for (int k = j - 1; k > -1; k--) {
- if (ma[i][k] == g) {
- // ещё 1 сторона
- for (int k1 = i - 1; k1 > -1; k1--) {
- if (ma[k1][k] == g) {
- if (ma[k1][j] == g) f = false;
- }
- if (!f) break;
- }
- if (!f) break;
- }
- if (!f) break;
- }
- if (f) {
- ex = false;
- ma[i][j] = g;
- if (j + 1 == m) rec(i + 1, 0);
- else rec(i, j + 1);
- ma[i][j] = 0;
- }
- if (allf) return;
- }
- if (ex) return;
- // проверка
- }// o(n*m*c-выбор)*c^(n*m) (найс скорость)
- }
- void rec1(int i, int j) {
- if (i == n) {
- for (int i1 = 0; i1 < n; i1++) {
- for (int j1 = 0; j1 < m; j1++) cout << ma[i1][j1] << " ";
- cout << "\n";
- }
- //char c;
- //cin >> c;
- //ans = ma;
- allf = true;
- }
- else {
- bool ex = true;
- for (int g = 1; g <= c; g++) {
- // выбираем цвет
- bool f = true;
- for (int k = j - 1; k > -1; k--) {
- if (ma[i][k] == g) {
- // ещё 1 сторона
- for (int k1 = i - 1; k1 > -1; k1--) {
- if (ma[k1][k] == g) {
- if (ma[k1][j] == g) f = false;
- }
- if (!f) break;
- }
- if (!f) break;
- }
- if (!f) break;
- }
- if (f) {
- ex = false;
- ma[i][j] = g;
- if (j + 1 == m) rec1(i + 1, 0);
- else rec1(i, j + 1);
- ma[i][j] = 0;
- }
- if (allf) return;
- }
- if (ex) return;
- // проверка
- }// o(n*m*c-выбор)*c^(n*m) (найс скорость)
- }
- int32_t main()
- {
- IOS;
- mt19937 rand;
- // rand.seed(std::time(nullptr));
- //for (int i1 = 2; i1 < 10; i1++) {
- //for (int j1 = 2; j1 < 10; j1++) {
- //n = i1;
- // m = i1;
- // c = 3;
- cin >> n >> m >> c;
- for (int i = 0; i < 10; i++) {
- for (int j = 0; j < 10; j++) ma[i][j] = 0;
- }
- //cin >> n >> m >> c;
- // создадим все подходящие (посмотреть)
- if (c==3)rec(0, 0);
- else rec1(0, 0);
- // for (int i = 0; i < n; i++) {
- // for (int j = 0; j < m; j++) cout << ans[i][j] << " ";
- // cout << "\n";
- // }
- //char c;
- // cin >> c;
- // }
- //}
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement