D. Block Tower
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
After too much playing on paper, Iahub has switched to computer games. The game he plays is called "Block Towers". It is played in a rectangular grid with n rows and m columns (it contains n × m cells). The goal of the game is to build your own city. Some cells in the grid are big holes, where Iahub can't build any building. The rest of cells are empty. In some empty cell Iahub can build exactly one tower of two following types:
Blue towers. Each has population limit equal to 100.
Red towers. Each has population limit equal to 200. However, it can be built in some cell only if in that moment at least one of the neighbouring cells has a Blue Tower. Two cells are neighbours is they share a side.
Iahub is also allowed to destroy a building from any cell. He can do this operation as much as he wants. After destroying a building, the other buildings are not influenced, and the destroyed cell becomes empty (so Iahub can build a tower in this cell if needed, see the second example for such a case).
Iahub can convince as many population as he wants to come into his city. So he needs to configure his city to allow maximum population possible. Therefore he should find a sequence of operations that builds the city in an optimal way, so that total population limit is as large as possible.
He says he's the best at this game, but he doesn't have the optimal solution. Write a program that calculates the optimal one, to show him that he's not as good as he thinks.
Input
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 500). Each of the next n lines contains m characters, describing the grid. The j-th character in the i-th line is '.' if you're allowed to build at the cell with coordinates (i, j) a tower (empty cell) or '#' if there is a big hole there.
Output
Print an integer k in the first line (0 ≤ k ≤ 106) — the number of operations Iahub should perform to obtain optimal result.
Each of the following k lines must contain a single operation in the following format:
«B x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — building a blue tower at the cell (x, y);
«R x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — building a red tower at the cell (x, y);
«D x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — destroying a tower at the cell (x, y).
If there are multiple solutions you can output any of them. Note, that you shouldn't minimize the number of operations.
Sample test(s)
input
2 3
..#
.#.
output
4
B 1 1
R 1 2
R 2 1
B 2 3
input
1 3
...
output
5
B 1 1
B 1 2
R 1 3
D 1 2
R 1 2
中文意思：
就是在 空的地方(字符'-')建造房子，藍色房子是100人口，紅色房子是200人口（建造紅色房子時，旁邊必須有藍色房子），要求人口最大，只需輸出可用的解就可以了。k是可行解的步數。
題解：
此題就是將盡可能的建造紅色房子，但要求在建造紅色房子時，它旁邊必須有個藍色房子。但輸出無順序要求。 首先我們將圖分成幾塊（被#完全隔開）。你可以發現這樣一點。你將所有的先全部建造成藍色，然後再慢慢的從邊際（也就是葉子）開始逐個的將此變成紅色。看樣例3，你就明白了。如此，每塊分割開的一個個塊將最後變成一個藍的房子跟紅色的其他房子。我們很容易知道，這時居住人口是最多的。因此，DFS即可解決這個問題。
因為n<=m<=500。我們的最大步數是3*m*n<k<=10^6次。所以這樣的解是可以的。
我們的k值就是 空房數量*3-藍色房子（一個塊只有1個）*2；k可以直接在DFS時出來（先壓點到棧）。
之後不斷彈出棧中元素，分別輸出 D操作跟R操作即可。。
/*
* @author ipqhjjybj
* @date 20130705
*
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#define clr(x,k) memset((x),(k),sizeof(x))
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;
char s[505][505];
int n,m;
struct node{
int x,y;
bool f; //表示是否為一個塊的開頭
node(){};
node(int xx,int yy,bool first){
x=xx,y=yy,f=first;
};
};
stack<node> sn;
bool visit[505][505];
int k;
int x1[4]={0,0,1,-1};
int y1[4]={1,-1,0,0};
#define legal(x,a) (1<=x&&x<=a)
void dfs(int xx,int yy){
int _x,_y,i;
for(i=0;i<4;i++){
_x=xx+x1[i],_y=yy+y1[i];
if(legal(_x,n)&&legal(_y,m)&&!visit[_x][_y]&&s[_x][_y]=='.'){
visit[_x][_y]=true;
sn.push(node(_x,_y,false));
dfs(_x,_y);
}
}
}
int main(){
// freopen("D.in","r",stdin);
int i,j;
while(scanf("%d %d",&n,&m)!=EOF){
getchar();
for(i=1;i<=n;i++)
gets(s[i]+1);
sn.empty();
k=0;
clr(visit,false);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if(!visit[i][j]&&s[i][j]=='.'){
k-=2;
visit[i][j]=true;
sn.push(node(i,j,true));
dfs(i,j);
}
}
k+=sn.size()*3;
printf("%d\n",k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(visit[i][j])
printf("B %d %d\n",i,j);
node t;
while(!sn.empty()){
t = sn.top(); sn.pop();
if(!t.f){
printf("D %d %d\n",t.x,t.y);
printf("R %d %d\n",t.x,t.y);
}
}
}
return 0;
}
