SRM 638 div1 easy ShadowSculpture

考えたこと

• Nが一個あったら該当する一列には置くことはできない
• おけないところを全て消し、置けるところだけからなる連結成分ごとに考えてよさそう
• 連結成分に全部置いたとして'Y'の条件を満たすような連結成分が存在するか判定するとよさそう
• 愚直な実装をしてもn<=10で何とかなりそうなので実装したら通った

3次元だとデバッグがつらくて大変…

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1, 0, 0}, dy[] = {1, 0, -1, 0, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1};

int cube[15][15][15], n;
bool used[15][15][15];
VVI vec;

void dfs(int x, int y, int z) {
  vec.PB({x, y, z});
  used[x][y][z] = true;
  REP(i, 6) {
    int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i];
    if(IN(0, n, nx) && IN(0, n, ny) && IN(0, n, nz) && !used[nx][ny][nz] && cube[nx][ny][nz] == 0) {
      dfs(nx, ny, nz);
    }
  }
}

class ShadowSculpture {
   public:
   string possible(vector <string> XY, vector <string> YZ, vector <string> ZX)
  {
    memset(cube, 0, sizeof(cube));
    memset(used, false, sizeof(used));
    VVI yes;
    n = XY.size();
    REP(i, n) REP(j, n) {
      if(XY[i][j] == 'N') {
        REP(k, n) cube[i][j][k] = -1;
      } else {
        yes.PB({i, j, -1});
      }
    }
    REP(i, n) REP(j, n) {
      if(YZ[i][j] == 'N') {
        REP(k, n) cube[k][i][j] = -1;
      } else {
        yes.PB({-1, i, j});
      }
    }
    REP(i, n) REP(j, n) {
      if(ZX[i][j] == 'N') {
        REP(k, n) cube[j][k][i] = -1;
      } else {
        yes.PB({j, -1, i});
      }
    }

    if(yes.size() == 0) {
      return "Possible";
    }

    // cube[i][j][k] = 0 の連結成分に全部おいてみて'Y'の条件を全部満たす
    REP(i, n) REP(j, n) REP(k, n) {
      bool ret = true;
      if(!used[i][j][k] && cube[i][j][k] == 0) {
        // (i, j, k) を含む連結成分を列挙する
        vec.clear();
        dfs(i, j, k);
        // Yの箇所の条件を全て満たせるか
        for(VI v1: yes) {
          int x = v1[0], y = v1[1], z = v1[2];
          bool flag = false;
          for(VI v2: vec) {
            if((v2[0] == x && v2[1] == y) ||
                (v2[1] == y && v2[2] == z) ||
                (v2[2] == z && v2[0] == x)) {
              flag = true;
              break;
            }
          }
          // 満たせないのが一つでもあったら
          if(!flag) {
            ret = false;
            break;
          }
        }
        // 全部条件を満たした
        if(ret) {
          return "Possible";
        }
      }
    }

    return "Impossible";
  }
};