应该是第一道没有看任何题解自己做出来的绿题了
题目传送门
看到题第一眼觉得应该写dfs, 大致脑补了流程(一次往一个方向dfs, 沿途做标记, 下一次从标记的点换方向dfs).
写完这个之后又尝试实现每一轮清除前一轮的点, 却在这里翻车了; 发现结果没有任何终点坐标标记 (效果类似于清除了地图上所有的*)
debug+想了一小时左右发现是因为dfs没写好, 结果会导致从刚标记的点开始继续往下dfs, 自己逻辑又没写对, 自然而然就清除了点.
试了几个PoC都不行, 最后想到正解: 开队列, 每次dfs完后push进上一轮的旧点, 再从旧点开始dfs标记本轮新点, 进入下一轮, 重复…… 有点像bfs
最后简单debug了一会儿之后就过了这题. 虽然200ms
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
64
65
66
67
68
69
| #include <iostream>
#include <queue>
using namespace std;
int n, m,t;
char a[55][55];
int si, sj;
bool in(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != 'X';
}
struct node{
int x, y;
node(int xx, int yy){
x = xx;
y = yy;
}
};
queue<node> q;
void dfs(string direction, int x, int y){
int dx = x, dy = y;
if(direction == "NORTH") dx--;
else if(direction == "SOUTH") dx++;
else if(direction == "EAST") dy++;
else if(direction == "WEST") dy--;
if(in(dx, dy)){
a[dx][dy] = '*';
dfs(direction, dx, dy);
}
}
int main(int argc, char *argv[]) {
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j]=='*'){
si=i, sj=j;
}
}
}
cin >> t;
string op;
cin >> op;
q.push(node(si, sj));
dfs(op, si, sj);
a[si][sj] = '.';
q.pop();
for(int i = 2; i <= t; i++){
cin >> op;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == '*') {
q.push(node(i, j));
a[i][j] = '.';
}
}
}
while(!q.empty()){
node tmpnode = q.front();
dfs(op, tmpnode.x, tmpnode.y);
q.pop();
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout << a[i][j];
}
cout << endl;
}
return 0;
}
|
确实是dfs好题
发现自己OI方面确实在gitting gud了
