問題
http://community.topcoder.com/stat?c=problem_statement&pm=10484&rd=13898
白と黒の２種類からなる２次元のセルがある。
ただし、そのうちのいくつかの黒のセルは折られており、左半分が白、右半分が
黒になっている。
ここからUnfoldlimit数だけ折られているセルを黒のセルに戻すことができる。
このとき、作ることのできる最大の三角形のセルの数を求める。
ただし、三角形は左上がすべて斜めのセルであり、右辺と下の辺は端、もしくは
白のセルで区切られており、中のセルはすべて黒のものとなる。
解き方
実装問題。上記の条件をコードに落とし込んでシンプルに実装する。
コード
int h,w;
class UnfoldingTriangles {
public:
bool can(vector<string> grid,int unfoldLimit,int r,int c,int len){
if(r+1<h)for(int j=c;j<c+len;j++)if(grid[r+1][j]=='#')return false;
if(c+len<w)for(int i=r;i>=r-len+1;i--)if(grid[i][c+len]=='#')return false;
for(int j=c;j<c+len;j++)if(grid[r-(j-c)][j]!='/')return false;
int cnt=0;
for(int j=c;j<c+len;j++){
for(int i=r;i>r-(j-c);i--){
if(grid[i][j]=='/')cnt++;
if(grid[i][j]=='.')return false;
}
}
return unfoldLimit>=cnt;
}
int solve(vector<string> grid, int unfoldLimit) {
h=grid.size(),w=grid[0].size();
int ret=-1;
FORE(i,0,h)FORE(j,0,w){
for(int len=1;len<=i+1&&len<=w-j;len++){
if(can(grid,unfoldLimit,i,j,len)){
int score= len==1 ? 1 : len*(len+1)/2;
ret=max(ret,score);
}
}
}
return ret;
}
};
class UnfoldingTriangles {
public:
bool can(vector<string> grid,int unfoldLimit,int r,int c,int len){
if(r+1<h)for(int j=c;j<c+len;j++)if(grid[r+1][j]=='#')return false;
if(c+len<w)for(int i=r;i>=r-len+1;i--)if(grid[i][c+len]=='#')return false;
for(int j=c;j<c+len;j++)if(grid[r-(j-c)][j]!='/')return false;
int cnt=0;
for(int j=c;j<c+len;j++){
for(int i=r;i>r-(j-c);i--){
if(grid[i][j]=='/')cnt++;
if(grid[i][j]=='.')return false;
}
}
return unfoldLimit>=cnt;
}
int solve(vector<string> grid, int unfoldLimit) {
h=grid.size(),w=grid[0].size();
int ret=-1;
FORE(i,0,h)FORE(j,0,w){
for(int len=1;len<=i+1&&len<=w-j;len++){
if(can(grid,unfoldLimit,i,j,len)){
int score= len==1 ? 1 : len*(len+1)/2;
ret=max(ret,score);
}
}
}
return ret;
}
};