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