C. Trapped in the Witch's Labyrinth（合理分配问号块的方向，使勇者困于迷宫中的块数最多） · znzryb
## 思路讲解
主要思路就是逆向思维，把所有能出去的点都识别出来，然后剩下的点就是不能出去的。
如果一个问号点周围都是能出去的，那么他也能出去。只要它周围有一个被困住的（不能出去），那么这个问号块也是被困住的。
然后主要是初始化上的一些细节问题
```cpp
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](https://codeforces.com/contest/2034/submission/297055462)
```cpp
#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](https://codeforces.com/contest/2034/submission/297053887)
没有注意思路中的初始化上的细节问题