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.
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.
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.
2 3
..#
.#.
4
B 1 1
R 1 2
R 2 1
B 2 3
1 3
...
5
B 1 1
B 1 2
R 1 3
D 1 2
R 1 2
【题解】
这是一道比较难想的dfs题，就是说，一个棋盘上，#的地方是石头，只有 . 的地方可以修建筑物，现在蓝色建筑物可以容纳100人，红色建筑物可以容纳200人，但是红色建筑物必须依赖于蓝色建筑物，换句话说，一个红色的建筑物周围上下左右至少要有一个蓝色建筑，所以这个题的突破点就是这，先把所有空的地方都设成蓝色建筑，对于每个分割的块，从某一点开始，先放上蓝色建筑，然后周围放上红色建筑，这就是连通块的题了，因为没有限制要最少步数， 每个蓝房子连通块内依次拆掉建红房子 ，最终就只剩下一个蓝房子了。
【AC代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int m,n;
char str[505][505];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool vis[505][505];struct node
{int i,j;bool f;node(){};node(int a,int b,bool ff){i = a;j = b;f = ff;}
};stack<node> ss;void dfs(int xx,int yy)
{for(int i=0;i<4;++i){int _x = xx+dx[i];int _y = yy+dy[i];if(_x>=1&&_x<=m&&_y>=1&&_y<=n&&!vis[_x][_y]&&str[_x][_y]=='.'){vis[_x][_y]=1;ss.push(node(_x,_y,0));dfs(_x,_y);}}
}int main()
{while(~scanf("%d%d",&m,&n)){getchar();while(!ss.empty())ss.pop();memset(vis,0,sizeof vis);for(int i=1;i<=m;++i)gets(str[i]+1);int s=0;for(int i=1;i<=m;++i)for(int j=1;j<=n;++j){if(!vis[i][j]&&str[i][j] == '.'){s-=2;vis[i][j] = 1;ss.push(node(i,j,1));dfs(i,j);}}s+=ss.size()*3;printf("%d\n",s);for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)if(vis[i][j])printf("B %d %d\n",i,j);while(!ss.empty()){node aa = ss.top();ss.pop();if(!aa.f){printf("D %d %d\n",aa.i,aa.j);printf("R %d %d\n",aa.i,aa.j);}}}return 0;
}