#include #define file_in(a) freopen(a, "r", stdin); #define file_out(a) freopen(a, "w", stdout); using namespace std; inline int sq(int a) { return a*a; } struct Cell { int row, col; Cell() {} Cell(int a, int b) : row(a), col(b) {} Cell operator+(const Cell &a) { Cell b; b.row = a.row + row; b.col = a.col + col; return b; } }; struct Field { int R; int G; int B; Field() {} Field(int a, int b, int c); void print(); }; Field mat[205][205]; Field goal[205][205]; struct Zone { Cell top; Cell bot; void print(); int calk(Zone a); Zone() {} Zone(Cell a, Cell b) : top(a), bot(b) {} bool operator<(const Zone &a) const { if(top.row == a.top.row) return top.col < a.top.col; return top.row < a.top.row; } bool operator>(const Zone &a) const { if(top.row == a.top.row) return top.col > a.top.col; return top.row > a.top.row; } bool operator==(const Zone &a) const { if(top.row == a.top.row and top.col == a.top.col) return true; return false; } }; struct State { int moves; string seq; int penalty; Cell cl; Cell start; State() {} State(int m, string s, int p, Cell c, Cell st); State& operator=(const State &a) { moves = a.moves; seq = a.seq; penalty = a.penalty; cl = a.cl; start = a.start; } }; Field :: Field(int a, int b, int c) : R(a), G(b), B(c) {} void Field :: print() { printf("(%d %d %d), ", R, G, B); } void Zone :: print() { for(int i = top.row; i <= bot.row; i++) { for(int j = top.col; j <= bot.col; j++) mat[i][j].print(); printf("\n"); } printf("\n"); } int Zone :: calk(Zone a) { int ret = 0; for(int i = top.row, k = a.top.row; i <= bot.row; i++, k++) { for(int j = top.col, q = a.top.col; j <= bot.col; j++, q++) { ret += sqrt(sq(mat[i][j].R - goal[k][q].R) + sq(mat[i][j].G - goal[k][q].G) + sq(mat[i][j].B - goal[k][q].B)); } } return ret; } State :: State(int m, string s, int p, Cell c, Cell st) : moves(m), seq(s), penalty(p), cl(c) { start = st; } typedef vector< vector > Grid; Grid puzzle; Grid gl; int Z; map d; char moveTo[4] = {'U', 'D', 'R', 'L'}; Cell addUp[4] = {Cell(-1, 0), Cell(1, 0), Cell(0, 1), Cell(0, -1)}; time_t TL = 9000; time_t curTime; time_t curTl = 1900; time_t patTime; int getDif(Grid a) { int dif = 0; for(int i = 0; i < a.size(); i++) for(int j = 0; j < a[i].size(); j++) dif += a[i][j].calk(gl[i][j]); return dif; } int priority(Grid a) { return d[a].moves + d[a].penalty; } struct Compare { bool operator()(Grid a, Grid b) { return priority(a) > priority(b); } }; bool noTime() { return clock() - curTime > TL; } priority_queue, Compare> q; void make_move(Grid a, Cell c, char to) { State temp = d[a]; int s1 = a[temp.cl.row][temp.cl.col].calk(gl[temp.cl.row][temp.cl.col]); int s2 = a[c.row][c.col].calk(gl[c.row][c.col]); int ns1 = a[temp.cl.row][temp.cl.col].calk(gl[c.row][c.col]); int ns2 = a[c.row][c.col].calk(gl[temp.cl.row][temp.cl.col]); int sum = (ns1 + ns2) - (s1 + s2); swap(a[temp.cl.row][temp.cl.col], a[c.row][c.col]); if(d.count(a) == 0/* and sum < 1*/) { d[a] = State(temp.moves + 1, temp.seq + to, temp.penalty + sum, c, temp.start); q.push(a); } } State best(0, "", INT_MAX, Cell(0, 0), Cell(0, 0)); void Solve(Cell start) { q.push(puzzle); d[puzzle] = State(0, "", getDif(puzzle), start, start); while(q.empty() == false) { Grid node = q.top(); q.pop(); if(d[node].penalty < best.penalty) best = d[node]; for(int i = 0; i < 4; i++) { if(clock() - curTime > 9000) return; Cell curCell(d[node].cl.row, d[node].cl.col); curCell = curCell + addUp[i]; if(curCell.row < 0) continue; if(curCell.col < 0) continue; if(curCell.row > (200 / Z - 1)) continue; if(curCell.col > (200 / Z - 1)) continue; make_move(node, curCell, moveTo[i]); } if(noTime()) return; if(clock() - patTime > curTl) return; } } void Input() { scanf("%d", &Z); for(int i = 0; i < 200; i++) { for(int j = 0; j < 200; j++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); mat[i][j] = Field(a, b, c); } } for(int i = 0; i < 200; i++) { for(int j = 0; j < 200; j++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); goal[i][j] = Field(a, b, c); } } for(int i = 0, k = 0; i < 200; i += Z, k++) { vector temp; for(int j = 0, q = 0; j < 200; j += Z, q++) { temp.push_back(Zone(Cell(i, j), Cell(i + Z - 1, j + Z - 1))); } puzzle.push_back(temp); gl.push_back(temp); } } bool used[200][200]; bool cmp(Cell a, Cell b) { return puzzle[a.row][a.col].calk(gl[a.row][a.col]) > puzzle[b.row][b.col].calk(gl[b.row][b.col]); } int main() { curTime = clock(); srand(time(NULL)); file_in("puzzle.in"); file_out("puzzle.out"); Input(); while(true) { if(noTime()) break; patTime = clock(); Cell tmp; tmp.row = rand() % (200 / Z - 1); tmp.col = rand() % (200 / Z - 1); if(used[tmp.row][tmp.col]) continue; used[tmp.row][tmp.col] = true; Solve(tmp); if(noTime()) break; d.empty(); if(noTime()) break; while(q.empty() == false) q.pop(); } //cout << best.penalty << endl; cout << best.start.row << " " << best.start.col << endl; cout << best.seq << endl; return 0; }