题意：
有一个网格图，上面有一些障碍，然后有a个入口，每个入口会进入一个机器人，机器人最初只会竖直向下走，然后可以放置一些转向装置，可强制机器人转向，问是否所有的机器人都能从出口出来。
题解：
每个格子的水平方向和竖直方向都只能被使用一次，因为两个机器人的路径不可能合并，也不可能迎面相撞。
如果一个格子没有放转弯装置，则可以被水平穿过一次，竖直穿过一次。如果一个格子放了转弯装置，则这个格子只能被一个机器人经过一次。
所以对于所有非障碍格子，可以拆成水平点和竖直点，每个点限流 1（即拆为出点和入点，容量均为1），上下相邻的格子连竖直点（竖直直行），左右相邻的格子连水平点（水平直行），格子内部的水平点和竖直点互相相连（转弯），源连向起点的竖直点，出口的竖直点连向汇，跑最大流，如果最大流 = 机器人个数，则输出 Yes，否则输出 No。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;
const int MAXM = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int T, n, m, bot, ext;
int mp[103][103];
int tot;
struct EDGE
{
int v, nxt, w;
} edge[MAXM << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
edge[ecnt].v = v, edge[ecnt].w = w, edge[ecnt].nxt = fir[u];
fir[u] = ecnt++;
swap(u, v);
edge[ecnt].v = v, edge[ecnt].w = 0, edge[ecnt].nxt = fir[u];
fir[u] = ecnt++;
}
int cur[MAXN], depth[MAXN];
int dfs(int u, int flow, int st, int ed)
{
if (u == ed)
return flow;
for (int &i = cur[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
int w = edge[i].w;
if (depth[v] == depth[u] + 1 && w)
{
int di = dfs(v, min(flow, w), st, ed);
if (di > 0)
{
edge[i].w -= di;
edge[i ^ 1].w += di;
return di;
}
}
}
return 0;
}
bool bfs(int st, int ed)
{
queue<int> q;
while (!q.empty())
q.pop();
memset(depth, 0, sizeof(depth));
depth[st] = 1;
q.push(st);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = fir[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
int w = edge[i].w;
if (depth[v] == 0 && w > 0)
{
depth[v] = depth[u] + 1;
q.push(v);
}
}
}
return depth[ed] > 0;
}
int dinic(int st, int ed)
{
int sum = 0;
while (bfs(st, ed))
{
for (int i = 0; i <= n * m * 4 + 1; i++)
cur[i] = fir[i];
while (int temp = dfs(st, inf, st, ed))
sum += temp;
}
return sum;
}
int getid(int x, int y, int id)
{
return id * n * m + (x - 1) * m + y;
}
/*
0 横点 入点
1 横点 出点
2 竖点 入点
3 竖点 出点
*/
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d%d", &n, &m, &bot, &ext);
memset(fir, -1, sizeof(fir));
ecnt = tot = 0;
for (int i = 1; i <= n; i++)
{
char str[103];
scanf("%s", str + 1);
for (int j = 1; j <= m; j++)
{
mp[i][j] = str[j] - '0';
if (mp[i][j])
continue;
addedge(getid(i, j, 0), getid(i, j, 1), 1);
addedge(getid(i, j, 1), getid(i, j, 2), 1);
addedge(getid(i, j, 2), getid(i, j, 3), 1);
addedge(getid(i, j, 3), getid(i, j, 0), 1);
}
}
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= m; j++)
if (!mp[i][j] && !mp[i + 1][j])
addedge(getid(i, j, 3), getid(i + 1, j, 2), 1);
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!mp[i][j] && !mp[i - 1][j])
addedge(getid(i, j, 3), getid(i - 1, j, 2), 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m - 1; j++)
if (!mp[i][j] && !mp[i][j + 1])
addedge(getid(i, j, 1), getid(i, j + 1, 0), 1);
for (int i = 1; i <= n; i++)
for (int j = 2; j <= m; j++)
if (!mp[i][j] && !mp[i][j - 1])
addedge(getid(i, j, 1), getid(i, j - 1, 0), 1);
for (int i = 1; i <= bot; i++)
{
int x;
scanf("%d", &x);
addedge(0, getid(1, x, 2), 1);
}
for (int i = 1; i <= ext; i++)
{
int x;
scanf("%d", &x);
addedge(getid(n, x, 3), n * m * 4 + 1, 1);
}
dinic(0, n * m * 4 + 1) == bot ? puts("Yes") : puts("No");
}
return 0;
}