[刷题] IDA*

BZOJ3041 水叮当的舞步

Description & Solution

见hzw的博客 http://hzwer.com/1507.html

Code

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 10;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int mp[N][N], mark[N][N], n, maxd, flag;

void dfs(int x, int y, int col) {
  mark[x][y] = 1;
  for (rint d = 0; d < 4; d++) {
    int fx = x + dx[d], fy = y + dy[d];
    if (fx >= 1 && fx <= n && fy >= 1 && fy <= n && mark[fx][fy] != 1) {
      mark[fx][fy] = 2;
      if (mp[fx][fy] == col) {
        dfs(fx, fy, col);
      }
    }    
  }
}
int h() {
  int cnt = 0, used[6] = {0};
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= n; j++) {
      if (!used[mp[i][j]] && mark[i][j] != 1) {
        used[mp[i][j]] = 1;
        cnt++;
      }
    }
  }
  return cnt;
}
int draw(int col) {
  int cnt = 0;
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= n; j++) {
      if (mp[i][j] == col && mark[i][j] == 2) {
        cnt++;
        dfs(i, j, col);
      }
    }
  }
  return cnt;
}
void search(int x) {
  if (flag) {
    return ;
  }
  int tar = h();
  if (!tar) flag = 1;
  if (flag) {
    return ;
  }
  if (x + tar > maxd) {
    return ;
  }
  int temp[N][N];
  for (rint i = 0; i <= 5; i++) {
    memcpy(temp, mark, sizeof(mark));
    if (draw(i)) search(x + 1);
    memcpy(mark, temp, sizeof(temp)); 
  }
}
int main() {
  while (~scanf("%d", &n) && n) {
    memset(mark, 0, sizeof(mark));
    memset(mp, 0, sizeof(mp));
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        mp[i][j] = read();
      }
    }
    dfs(1, 1, mp[1][1]);
    flag = 0;
    for (maxd = 0; ; maxd++) {
      search(0);
      if (flag) break;
    }
    printf("%d
", maxd);
  }
  return 0;
}