## 2013年8月26日

### UVa 1008 - A Vexing Problem

time limit: 54.000 seconds run : 52.472
lol
```#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#define MP make_pair
#define PB push_back
using namespace std;

typedef pair<int, int> P;
typedef vector<P> VP;
typedef vector<string> VS;

struct State {
VS puzzle, path;
VP remain;
};

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};
int R, C;
char name[99];

bool fall(VS & puzzle, VP & remain) {
bool moved = false;
for (int i = remain.size() - 1; i >= 0; i--) {
int r = remain[i].first, c = remain[i].second;
while (puzzle[r + 1][c] == '-') {
moved = true;
puzzle[r + 1][c] = puzzle[r][c];
puzzle[r++][c] = '-';
remain[i].first++;
}
}
return moved;
}

void remove(VS & puzzle, VP & remain) {
bool removed[100] = {};
for (int i = 0; i < remain.size(); i++) {
for (int j = i + 1; j < remain.size(); j++) {
int r1 = remain[i].first, c1 = remain[i].second;
int r2 = remain[j].first, c2 = remain[j].second;
if (puzzle[r1][c1] == puzzle[r2][c2]) {
for (int d = 0; d < 4; d++) {
if (r1 + dr[d] == r2 && c1 + dc[d] == c2) {
removed[i] = removed[j] = true;
}
}
}
}
}
VP newRemain;
for (int i = 0; i < remain.size(); i++) {
if (removed[i]) {
int r = remain[i].first, c = remain[i].second;
puzzle[r][c] = '-';
} else {
newRemain.PB(remain[i]);
}
}
remain = newRemain;
}

void solve(VS & puzzle, VP & remain) {
fall(puzzle, remain);
remove(puzzle, remain);
while (fall(puzzle, remain)) {
remove(puzzle, remain);
}
}

void showPath(VS & path) {
printf("%s: Minimum solution length = %d\n", name, path.size());
for (int i = 0; i < path.size(); i++) {
printf("%s%s", path[i].c_str(), (i < path.size() - 1) ? ((i % 4 == 3) ? "\n" : " ") : "\n");
}
}

void BFS(const VS & initPuzzle, const VP & initRemain) {
VS puzzle = initPuzzle, path;
VP remain = initRemain;
map<VS, int> dis[100];
dis[remain.size()][puzzle] = 0;
queue<State> q;
q.push((State){puzzle, path, remain});
while (!q.empty()) {
puzzle = q.front().puzzle;
path = q.front().path;
remain = q.front().remain;
int d = dis[remain.size()][puzzle];
q.pop();
if (!remain.size()) {
showPath(path);
return;
}
for (int i = 0; i < remain.size(); i++) {
int r = remain[i].first, c = remain[i].second;
for (int dc = -1; dc <= 1; dc += 2) {
if (puzzle[r][c + dc] == '-') {
VS newPuzzle = puzzle;
newPuzzle[r][c + dc] = newPuzzle[r][c];
newPuzzle[r][c] = '-';
VP newRemain = remain;
newRemain[i].second += dc;
solve(newPuzzle, newRemain);
if (dis[newRemain.size()].find(newPuzzle) == dis[newRemain.size()].end()) {
dis[newRemain.size()][newPuzzle] = d + 1;
VS newPath = path;
newPath.PB("(" + string(1, puzzle[r][c]) + "," + string(1, r + '0') + "," + string(1, c + '0') + "," + (dc == -1 ? "L" : "R") + ")");
if (!newRemain.size()) {
showPath(newPath);
return;
}
q.push((State){newPuzzle, newPath, newRemain});
}
}
}
}
}
}

int main() {
while (scanf("%d%d%s", &R, &C, name) && R) {
VS puzzle;
char s[99];
for (int r = 0; r < R; r++) {
scanf("%s", s);
puzzle.PB(s);
}
VP remain;
for (int r = 0; r < puzzle.size() - 1; r++) {
for (int c = 1; puzzle[r][c + 1]; c++) {
if (puzzle[r][c] != '#' && puzzle[r][c] != '-') {
remain.PB(MP(r, c));
}
}
}
BFS(puzzle, remain);
}
return 0;
}
```