codeforces Block Tower

本文从WordPress迁移而来, 查看全部WordPress迁移文章

http://codeforces.com/contest/327/problem/D

简单搜索

题意:给一个n*m的矩阵图,一开始只有.和#,表示可以空地可以放东西和岩石不能放。在空地上可以任意放蓝块,蓝块有100人。空地也可以放红块,但是要求这个空地四周(上下左右)必须已经有一个蓝块,红色有200人。另外已经放了块的地方,可以毁掉,重新放想要的块。问最后矩阵图里面最多放多少人。不需要输出人数,而是输出整个摆放的步骤。
这题其实是水题,看sample 2没有认真看,放红块仅仅是放的时候有要求,但是放了之后是没要求的,即放之前之前至少 有一个蓝块,但是放之后四周可以没有蓝块。

摆放策略:dfs遍历掉所有的空地,没到一个空地就将空地变蓝。dfs完了返回时在蓝块毁掉,再放红块。但是有一个例外,就是 dfs的起点要保留蓝块。最后,矩阵图中有多少大块连续的空地,就有多少个蓝块,其余空地都是红块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 510;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int n,m;
char map[N][N];
bool vis[N][N];
struct opp{
char c;
int x,y;
opp(char ch ,int a ,int b){
c = ch; x = a; y = b;
}
};
vector<opp>a;

inline bool check(int x , int y){
if(x < 1 || x > n || y < 0 || y > m)
return false;
return true;
}

void dfs(int x,int y,int start){
vis[x][y] = true;
a.push_back(opp('B',x,y));
for(int i = 0; i < 4; i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(check(xx,yy) && !vis[xx][yy] && map[xx][yy] == '.')
dfs(xx,yy,false);
}
if(!start){
a.push_back(opp('D',x,y));
a.push_back(opp('R',x,y));
map[x][y] = 'R'; //不需要,只是为了打印最后的地图
}
else
map[x][y] = 'B'; //不需要,只是为了打印最后的地图
}

int main(){
a.clear();
memset(vis,false,sizeof(vis));
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%s",map[i] + 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(!vis[i][j] && map[i][j] == '.')
dfs(i,j,true);
cout << a.size() << endl;
for(int i = 0; i < a.size(); i++)
printf("%c %d %d\n",a[i].c,a[i].x,a[i].y);

// for(int i = 1; i <= n; i++)
// printf("%s\n",map[i] + 1);
return 0;
}