题目链接：https://cn.vjudge.net/contest/283918#problem/C
题目大意：T个测试数据，然后给你一个字符串，每一个字符串包括‘s’，‘t’，‘o’，‘#’，‘.’ 。's'代表起点，‘t’代表终点，‘o’代表传送门（传送门之间可以无限次互相到达），‘#’代表墙壁，‘.’代表空的房间，一个人从s开始，只要不是‘#‘，他都可以走进去，然后问你最少填满几个房间，才能使得无论如何s到达不了t，如果不存在正解的话，输出-1.
具体思路：一个搜索题硬生生搞成了网络流？就是拆点限制流量就可以了，注意拆点。对于传送门，我们可以都统一指向一个点，然后再由这个点连向所有的传送门就可以了，这样就不用两重for互相连边了。
AC代码：
#include<iostream>
#include<stack>
#include<queue>
#include<iomanip>
#include<stdio.h>
#include<cstring>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
# define ll long long
const int maxn = 5e5+;
const int inf = 0x3f3f3f3f;
int pprev[maxn];
int head[maxn];
char str[maxn];
int sto[maxn];
struct node
{
int to;
int flow;
int nex;
} edge[maxn<<];
int num,st,ed,n;
void addedge(int fr,int to,int flow)
{
edge[num].to=to;
edge[num].flow=flow;
edge[num].nex=head[fr];
head[fr]=num++;
edge[num].to=fr;
edge[num].flow=;
edge[num].nex=head[to];
head[to]=num++;
}
bool bfs()
{
// memset(prev,-1,sizeof(prev));
for(int i=;i<=*n+;i++)pprev[i]=-;
pprev[st]=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int top=q.front();
q.pop();
for(int i=head[top]; i!=-; i=edge[i].nex)
{
int temp=edge[i].to;
if(pprev[temp]==-&&edge[i].flow>)
{
pprev[temp]=pprev[top]+;
q.push(temp);
}
}
}
return pprev[ed]!=-;
}
int dfs(int u,int flow)
{
if(u==ed)
return flow;
int res=;
for(int i=head[u]; i!=-; i=edge[i].nex)
{
int t=edge[i].to;
if(pprev[t]==(pprev[u]+)&&edge[i].flow>)
{
int temp=dfs(t,min(flow,edge[i].flow));
edge[i].flow-=temp;
edge[i^].flow+=temp;
res+=temp;
flow-=temp;
if(flow==)
break;
}
}
if(res==)
pprev[u]=-;
return res;
}
int dinic()
{
int ans=;
while(bfs())
{
ans+=dfs(st,inf);
}
return ans;
}
int main()
{
// freopen("portals.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int sum=;
scanf("%d",&n);
scanf("%s",str);
for(int i=; i<=*n+; i++)
{
head[i]=-;
}
num=;
for(int i=;i<n;i++){//其实这里起点和终点不拆点也没问题，只不过为了下一个for循环方便连边。
if(str[i]=='s')st=i,addedge(i,n+i,inf);
if(str[i]=='e')ed=i,addedge(i,i+n,inf);
if(str[i]=='.')addedge(i,n+i,);
if(str[i]=='o')addedge(i,n+i,inf);
}
// cout<<st<<" "<<ed<<endl;
for(int i=;i<n-;i++){
if(str[i]!='#'&&str[i+]!='#'){
addedge(i+n,i+,inf);
addedge(i++n,i,inf);
}
}
//addedge()
for(int i=;i<n;i++){
if(str[i]!='o')continue;
addedge(i+n,n*+,inf);
addedge(n*+,i,inf);
}
addedge(n*+,n*+,inf);
int ans=dinic();
printf("%d\n",ans==inf?-:ans);
}
return ;
}