Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <set>
- #include <stack>
- #include <cmath>
- #include <random>
- #include <ctime>
- #include <fstream>
- using namespace std;
- int n;
- struct shift {
- int n, s;
- char d;
- shift(int tn, char td, int ts): n(tn), d(td), s(ts) { }
- };
- int dist(int x0, int y0, int x1, int y1) {
- if (y0 == y1) {
- return 4;
- } else {
- return 3;
- }
- }
- void make_shift(int x, char d, int s, vector<vector<int>> &v, vector<shift> &ans) {
- ans.push_back(shift(x, d, s));
- if (d == 'U') {
- vector<int> tmp(n);
- for (int i = 0; i < n; i++) {
- int posx = i + s;
- if (posx >= n) {
- posx -= n;
- }
- tmp[i] = v[posx][x];
- }
- for (int i = 0; i < n; i++) {
- v[i][x] = tmp[i];
- }
- } else if (d == 'R') {
- vector<int> tmp(n);
- for (int i = 0; i < n; i++) {
- int posx = i - s;
- if (posx < 0) {
- posx += n;
- }
- tmp[i] = v[x][posx];
- }
- for (int i = 0; i < n; i++) {
- v[x][i] = tmp[i];
- }
- } else if (d == 'D') {
- vector<int> tmp(n);
- for (int i = 0; i < n; i++) {
- int posx = i - s;
- if (posx < 0) {
- posx += n;
- }
- tmp[i] = v[posx][x];
- }
- for (int i = 0; i < n; i++) {
- v[i][x] = tmp[i];
- }
- } else if (d == 'L') {
- vector<int> tmp(n);
- for (int i = 0; i < n; i++) {
- int posx = i + s;
- if (posx >= n) {
- posx -= n;
- }
- tmp[i] = v[x][posx];
- }
- for (int i = 0; i < n; i++) {
- v[x][i] = tmp[i];
- }
- }
- }
- void apply(int x0, int y0, int x1, int y1, vector<vector<int>> &v, vector<shift> &ans) {
- if (y0 == y1) {
- make_shift(x0, 'R', 1, v, ans);
- make_shift(y1, 'D', x0 - x1, v, ans);
- make_shift(x0, 'L', 1, v, ans);
- make_shift(y1, 'U', x0 - x1, v, ans);
- } else {
- make_shift(y1, 'D', x0 - x1, v, ans);
- int delta = y0 - y1;
- if (delta < 0) {
- delta += n;
- }
- make_shift(x0, 'L', delta, v, ans);
- make_shift(y1, 'U', x0 - x1, v, ans);
- }
- }
- int main() {
- int t;
- cin >> t;
- cout << t << endl;
- while (t--) {
- cin >> n;
- vector<vector<int>> tv(n, vector<int>(n));
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- cin >> tv[i][j];
- }
- }
- vector<int> colors(n);
- for (int i = 0; i < n; i++) {
- colors[i] = i;
- }
- int best_ans = 1000 * 1000 * 1000;
- vector<shift> final_ans;
- for (int iter = 0; iter < 10000; iter++) {
- vector<shift> ans;
- vector<vector<int>> v(tv);
- for (int row = 0; row < n; row++) {
- int color = colors[row];
- vector<int> positions;
- vector<bool> used;
- for (int col = 0; col < n; col++) {
- if (v[row][col] != color) {
- positions.push_back(col);
- used.push_back(false);
- }
- }
- for (int z = 0; z < n; z++) {
- for (int i = row + 1; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (v[i][j] == color) {
- int cur_best = 100, best_ind = -1;
- for (int t = 0; t < positions.size(); t++) {
- if (used[t]) {
- continue;
- }
- if (dist(i, j, row, positions[t]) < cur_best) {
- cur_best = dist(i, j, row, positions[t]);
- best_ind = t;
- }
- }
- used[best_ind] = true;
- apply(i, j, row, positions[best_ind], v, ans);
- }
- }
- }
- }
- }
- if (best_ans > ans.size()) {
- best_ans = (int) ans.size();
- final_ans = ans;
- }
- random_shuffle(colors.begin(), colors.end());
- }
- cout << final_ans.size() << endl;
- for (int i = 0; i < final_ans.size(); i++) {
- cout << final_ans[i].n << ' ' << final_ans[i].d << ' ' << final_ans[i].s << endl;
- }
- }
- }
- //* * * * * ok
- //* * * * * ok
- //* * * b * cur
- //* * * * *
- // * * * a *
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement