問題
http://community.topcoder.com/stat?c=problem_statement&pm=9752&rd=12183
座標(0,0)を中心として、１辺の長さがcakeLength*2であり、中心の穴がholeLength*2であるケーキが存在する。
このケーキを、あらかじめ与えられたy軸に平行なカットとx軸に平行なカットを行ったときに最終的に残るカットされたケーキの数を求める。
解き方
(0,0)が中心というのを最初見落としてしまい、時間がかかってしまった。
(0,0)→(cakeLength,cakeLength)となるように座標変換して
左上が(0,0)にくるようにして、各カットのまとまりごとにdfsを回して答えを求める。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int used[200][200],vcut[200],hcut[200],n;
class HoleCakeCuts {
public:
void dfs(int i,int j){
if(used[i][j])return;
used[i][j]=1;
if(i>0&&!vcut[i-1])dfs(i-1,j);
if(i<n-1&&!vcut[i])dfs(i+1,j);
if(j>0&&!hcut[j-1])dfs(i,j-1);
if(j<n-1&&!hcut[j])dfs(i,j+1);
}
int cutTheCake(int cake, int hole, vector<int> h, vector<int> v) {
n=cake*2;
memset(used,0,sizeof(used));
FORE(i,cake-hole,cake+hole)FORE(j,cake-hole,cake+hole)used[i][j]=1;
memset(vcut,0,sizeof(vcut));
FORE(i,0,v.size())vcut[v[i]+cake-1]=1;
memset(hcut,0,sizeof(hcut));
FORE(i,0,h.size())hcut[h[i]+cake-1]=1;
int ret=0;
FORE(i,0,cake*2){
FORE(j,0,cake*2){
if(used[i][j])continue;
ret++;
dfs(i,j);
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int used[200][200],vcut[200],hcut[200],n;
class HoleCakeCuts {
public:
void dfs(int i,int j){
if(used[i][j])return;
used[i][j]=1;
if(i>0&&!vcut[i-1])dfs(i-1,j);
if(i<n-1&&!vcut[i])dfs(i+1,j);
if(j>0&&!hcut[j-1])dfs(i,j-1);
if(j<n-1&&!hcut[j])dfs(i,j+1);
}
int cutTheCake(int cake, int hole, vector<int> h, vector<int> v) {
n=cake*2;
memset(used,0,sizeof(used));
FORE(i,cake-hole,cake+hole)FORE(j,cake-hole,cake+hole)used[i][j]=1;
memset(vcut,0,sizeof(vcut));
FORE(i,0,v.size())vcut[v[i]+cake-1]=1;
memset(hcut,0,sizeof(hcut));
FORE(i,0,h.size())hcut[h[i]+cake-1]=1;
int ret=0;
FORE(i,0,cake*2){
FORE(j,0,cake*2){
if(used[i][j])continue;
ret++;
dfs(i,j);
}
}
return ret;
}
};