Submission #1633033

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

int N;
int H , W;
vector<int> A;
vector<vector<int>> MAP;
int G[20][20];
int visited[20];
vector<int> g;

int dfs(vector<int> &g, int v) {
  if(visited[v] == false) {
    visited[v] = true;
    for(int i = 0; i < N; i++) {
      if(G[v][i] < 0) dfs(g, i);
    }
    g.push_back(v);
  }
}

map<pair<int, int>,bool> dp[20][20];
int solve(int no, int bits, int same, int pos) {
  auto p = make_pair(no, bits);
  if(dp[no][pos].count(p)) return dp[no][pos][p];
  bool same_color = no < N - 1 && A[no] == A[no + 1];
  if(no == N) return 1;
  if(pos == N) return 0; // 失敗
  int ret = solve(no, bits, same, pos + 1);
  if(bits >> pos & 1) return dp[no][pos][p] = ret;
  for(int i = 0; i < N; i++) {
    if(G[pos][i] < 0 && bits >> i & 1) return dp[no][pos][p]= 0; // 先が塗られているなら無理
    if(G[i][pos] < 0 && same >> i & 1) return dp[no][pos][p]= ret; // 同じ色で塗られていたらもう塗れない
  }
  ret |= solve(no + 1, bits | (1 << pos), same_color ? (same | (1 << pos)) : 0, same_color ? pos + 1: 0);
  return dp[no][pos][p]=ret;
}
int main() {
  cin >> N;
  A=vector<int>(N);
  for(int&a:A)cin>>a;
  sort(A.begin(), A.end());
  cin >> H >> W;
  MAP=vector<vector<int>>(H, vector<int>(W));
  for(int y = 0; y < H; y++) {
    for(int x = 0; x < W; x++) {
      cin>>MAP[y][x];
    }
  }
  for(int i = 0; i < N; i++) {
    fill(G[i], G[i]+N, 99999999);
    G[i][i] = 0;
  }
  for(int i = 0; i < N; i++) {
    int min_x = 2000, max_x = -1;
    int min_y = 2000, max_y = -1;
    for(int y = 0; y < H; y++) {
      for(int x = 0; x < W; x++) {
        if(MAP[y][x] == i) {
          min_x = min(min_x, x);
          min_y = min(min_y, y);
          max_x = max(max_x, x);
          max_y = max(max_y, y);
        }
      }
    }
    for(int y = min_y; y <= max_y; y++) {
      for(int x = min_x; x <= max_x; x++) {
        if(MAP[y][x] != i) {
          G[i][MAP[y][x]] = -1;
        }
      }
    }
  }
  for(int k = 0; k < N; k++)
    for(int i = 0; i < N; i++)
      for(int j = 0;j < N; j++){
        G[i][j] = min(G[i][j], G[i][k]+ G[k][j]);
      }
  for(int i = 0; i < N; i++) {
    if(G[i][i] < 0) {
      cout << 0 << endl;
      return 0;
    }
  }
  for(int i = 0; i < N; i++) {
    dfs(g, i);
  }
  reverse(g.begin(), g.end());
  cout << solve(0, 0, 0, 0) << endl;
}

Submission Info

Judge Result