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;
}

沒有留言:

張貼留言