[Blog] [Docs] [Code] [Slides] [About]

2014 Xi'an Regional B - Puzzle & Dragons

模拟

2020-03-26 16:37 CST

Problem

题目链接(CodeForces)

经典模拟题。CF上的15s时限最后只用了6115ms。

Debug吐了。优化策略:

  • 不走回头路,使得搜索$4^n$降为$3^n$;
  • 双指针处理下落,处理时间由$n^2$降为$n$。

Solution

#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define DEBUG
#else
#define DEBUG(str) cout << str << endl;
#endif
using namespace std;
const int INF = 0x3f3f3f3f;
const int H = 5, W = 6;
 
const int dx[5] = {0, 1, -1, 0, 0};
const int dy[5] = {0, 0, 0, 1, -1};
const char dn[5] = {'O', 'D', 'U', 'R', 'L'};
const char rn[5] = {'O', 'U', 'D', 'L', 'R'};
char str[6][12] = {};
 
bool valid(int x, int y) { return x >= 1 and x <= H and y >= 1 and y <= W; }
 
class Score {
 public:
  int combo, drop, length;
  int posx, posy;
  char path[12];
  bool isWorseThan(int c, int d, int l) {
    return combo < c or (combo == c and drop < d) or
           (combo == c and drop == d and length > l);
  }
};
 
class Game {
 private:
  int board[6][7];
  int current[6][7];
  int eliminated[6][7];
  char path[12];
  int orix, oriy;
  Score best;
 
 public:
  void dump() {
    printf("-------------------\n");
    for (int x = 1; x <= H; ++x) {
      for (int y = 1; y <= W; ++y) {
        if (current[x][y] > 0) {
          if (eliminated[x][y]) {
            printf("%c", tolower(current[x][y]));
          } else {
            printf("%c", current[x][y]);
          }
        } else {
          printf("-");
        }
      }
      printf("\n");
    }
  }
  Game() {
    for (int x = 1; x <= H; ++x) {
      for (int y = 1; y <= W; ++y) {
        board[x][y] = str[x][y - 1];
      }
    }
    memset(path, 0, sizeof(path));
    memset(eliminated, 0, sizeof(eliminated));
    best.combo = best.drop = 0, best.length = INF;
  }
  Score solve() {
    for (int x = 1; x <= H; ++x) {
      for (int y = 1; y <= W; ++y) {
        orix = x, oriy = y;
        dfs(x, y, 0);
        // DEBUG(x << " " << y << " -> " << score.combo << " " << score.path);
      }
    }
    return best;
  }
  void dfs(int x, int y, int pos) {
    if (!valid(x, y)) return;
    if (pos >= 9) {
      eliminate(pos);
    } else {
      if (pos > 0) {
        eliminate(pos);
      }
      for (int i = 1; i <= 4; ++i) {
        if (pos == 0 or path[pos - 1] != rn[i]) {
          int nx = x + dx[i], ny = y + dy[i];
          swap(board[x][y], board[nx][ny]);
          path[pos] = dn[i];
          dfs(nx, ny, pos + 1);
          path[pos] = '\0';
          swap(board[x][y], board[nx][ny]);
        }
      }
    }
  }
  void eliminate(int length) {
    // DEBUG(" -> " << path);
    memcpy(current, board, sizeof(current));
    int combo = 0, drop = 0;
    bool hasMore = true;
    while (hasMore) {
      hasMore = false;
      // Horizontal scan
      // DEBUG("  -> Horizontal scan");
      for (int x = 1; x <= H; ++x) {
        for (int y = 1; y <= W - 2; ++y) {
          if (current[x][y] == -1) continue;
          if (current[x][y] == current[x][y + 1] and
              current[x][y] == current[x][y + 2]) {
            hasMore = true;
            eliminated[x][y] = eliminated[x][y + 1] = eliminated[x][y + 2] =
                current[x][y];
          }
        }
      }
      // Vertical scan
      // DEBUG("  -> Vertical scan");
      for (int y = 1; y <= W; ++y) {
        for (int x = 1; x <= H - 2; ++x) {
          if (current[x][y] == -1) continue;
          if (current[x][y] == current[x + 1][y] and
              current[x][y] == current[x + 2][y]) {
            hasMore = true;
            eliminated[x][y] = eliminated[x + 1][y] = eliminated[x + 2][y] =
                current[x][y];
          }
        }
      }
      if (!hasMore) break;
      // Count for answer
      // DEBUG("  -> Counting delta");
      // if (orix == 4 and oriy == 3 and !strcmp(path, "RURURDLDD")) dump();
      for (int x = 1; x <= H; ++x) {
        for (int y = 1; y <= W; ++y) {
          if (eliminated[x][y]) {
            ++combo;
            drop += dfs2(x, y, eliminated[x][y]);
          }
        }
      }
      // DEBUG(combo << " " << drop);
      // Update current board
      // DEBUG("  -> Updating map");
      for (int y = 1; y <= W; ++y) {
        int bottom = H;
        for (int x = H; x >= 1; --x) {
          if (current[x][y] != -1) {
            if (bottom != x) {
              current[bottom][y] = current[x][y];
              current[x][y] = -1;
            }
            --bottom;
          }
        }
      }
    }
    // Update the global best answer
    if (best.isWorseThan(combo, drop, length)) {
      best.combo = combo;
      best.drop = drop;
      best.length = length;
      best.posx = orix;
      best.posy = oriy;
      strcpy(best.path, path);
    }
  }
  int dfs2(int x, int y, int val) {
    if (valid(x, y) and eliminated[x][y] == val) {
      int ret = 1;
      current[x][y] = -1;  // eliminate from map
      eliminated[x][y] = 0;
      for (int i = 1; i <= 4; ++i) {
        ret += dfs2(x + dx[i], y + dy[i], val);
      }
      return ret;
    } else {
      return 0;
    }
  }
};
 
int main() {
  int T = 0;
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) {
    for (int i = 1; i <= 5; ++i) {
      scanf(" %s", str[i]);
    }
    Game game;
    Score ans = game.solve();
    printf("Case #%d:\nCombo:%d Length:%d\n%d %d\n%s\n", t, ans.combo,
           ans.length, ans.posx, ans.posy, ans.path);
  }
}
<EOF>