Znzryb's Blog
0%

C. Trapped in the Witch's Labyrinth（合理分配问号块的方向，使勇者困于迷宫中的块数最多）

Posted on Edited on

思路讲解

主要思路就是逆向思维，把所有能出去的点都识别出来，然后剩下的点就是不能出去的。

如果一个问号点周围都是能出去的，那么他也能出去。只要它周围有一个被困住的（不能出去），那么这个问号块也是被困住的。

然后主要是初始化上的一些细节问题

1
2
3
4
memset(isStuck, false, sizeof(isStuck));
for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
		isStuck[i][j]=true;

所有外面的块提前被设为不被困住，里面的块设为可以困住的

然后按照这个做法做就完了。

AC代码

https://codeforces.com/contest/2034/submission/297055462

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
// https://codeforces.com/contest/2034/problem/C
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,m;
char maze[1010][1010];
bool vis[1010][1010],isStuck[1010][1010];
map<char,array<int, 2> > dir={{'U',{-1,0}},{'D',{1,0}},{'L',{0,-1}},{'R',{0,1}}};
map<char,char> reverseMap={{'U','D'},{'D','U'},{'L','R'},{'R','L'}};
ll mans;
// 我稍微看了一眼题解，大概猜到思路了
// 就是顺着走直接走出去的方块一定没救

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

void dfs(int x,int y){
	if(isOut(x, y))
		return;
	if(maze[x][y]=='?')
		return;
	if(vis[x][y])
		return;
	isStuck[x][y]=false;
	vis[x][y]=true;
	mans+=1;
//	char dirc=reverseMap[maze[x][y]];
//	int nx=x+dir[dirc][0],ny=y+dir[dirc][1];
	// 如果说要去的那个格子之前可以到你这个格子
	// 那么就是可以去的
	vector<ll> xdir={0,1,0,-1};
	vector<ll> ydir={1,0,-1,0};
	for(int i=0;i<4;++i){
		int nx=x+xdir[i],ny=y+ydir[i];
		if(isOut(nx, ny))
			continue;
		if(nx+dir[maze[nx][ny]][0]==x && ny+dir[maze[nx][ny]][1]==y){
			dfs(nx, ny);
		}
	}
	
	
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n>>m;
//		memset(maze, '0', sizeof(maze));
//		vector<vector<char>> maze(n+10,vector<char>(m+10));
		memset(vis, false, sizeof(vis));
		memset(isStuck, false, sizeof(isStuck));
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				isStuck[i][j]=true;
		mans=0;
		for(int i=1;i<=n;++i){
			for (int j=1; j<=m; ++j) {
				cin>>maze[i][j];
				
//				reverseMaze[i][j]=reverseMap[maze[i][j]];
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(maze[i][j]=='?')
					continue;
				char dirc=maze[i][j];	
				// 反正时间复杂度无所谓，用稍微复杂点的写法
				// 指的是我们能走出去的点，才能进入
				if(isOut(i+dir[dirc][0], j+dir[dirc][1]))
					isStuck[i][j]=false,dfs(i, j);
			}
		}
		
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(maze[i][j]!='?')
					continue;
				vector<ll> xdir={0,1,0,-1};
				vector<ll> ydir={1,0,-1,0};
				bool isBreak=false;
				for(int k=0;k<4;++k){
					if(isStuck[i+xdir[k]][j+ydir[k]]){
						isBreak=true;
						break;
					}
				}
				if(!isBreak)
					mans+=1;
			}
		}
		cout<<n*m-mans<<endl;
	}
	return 0;
}
// AC https://codeforces.com/contest/2034/submission/297055462
/*
3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL

0
6
5

1
3 3
?U?
L?R
?D?

0
*/

心路历程（WA，TLE，MLE……）

WA：

https://codeforces.com/contest/2034/submission/297053887

没有注意思路中的初始化上的细节问题