AOJ_1030 Cubes Without Holes
問題
解法
小さい立方体の状態は次の4とおり
(a)とり除かれていない
(b)1つ以上の方向からの穴によってとり除かれる
(c)2つ以上の方向からの穴によってとり除かれる
(d)3つの方向からの穴によってとり除かれる
求める答えaは
a = n^3-(bの個数)+(cの個数)-(dの個数)
b,c,dの個数は簡単に求められる
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_H = 200; typedef pair<int, int> P; vector<P> xyz[3]; int n, h; int main(){ int a, b; char xyz_[4], c; while(scanf("%d %d", &n, &h) && (n || h)){ for(int i=0;i<3;i++) xyz[i].clear(); for(int i = 0; i < h; i++){ scanf("%c", &c); scanf("%s", xyz_); scanf("%d %d", &a, &b); if(xyz_[0] == 'x' && xyz_[1] == 'y'){ xyz[0].push_back(P(a, b)); }else if(xyz_[0] == 'x' && xyz_[1] == 'z'){ xyz[2].push_back(P(b, a)); }else if(xyz_[0] == 'y' && xyz_[1] == 'z'){ xyz[1].push_back(P(a, b)); } } int ans = n * n * n; P p1, p2, p3; //3方向から穴がある立方体 for(int i = 0; i < xyz[0].size(); i++){ p1 = xyz[0][i]; for(int j = 0; j < xyz[1].size(); j++){ p2 = xyz[1][j]; for(int k = 0; k < xyz[2].size(); k++){ p3 = xyz[2][k]; if(p1.second==p2.first && p2.second==p3.first && p3.second==p1.first){ ans--; } } } } //2方向以上から穴がある立方体 for(int k = 0; k < 3; k++){ for(int i = 0; i < xyz[k].size(); i++){ p1 = xyz[k][i]; for(int j = 0; j < xyz[(k+1)%3].size(); j++){ p2 = xyz[(k+1)%3][j]; if(p1.second==p2.first){ ans++; } } } } ans -= n * h; printf("%d\n", ans); } return 0; }
setを知ったのはこの後である。orz