CCPC 2019 진 황도 - 탈출

Escape
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 0 Accepted Submission(s): 0
Problem Description n 하나만 주세요.×m 크기 의 미로, 왼쪽 상단 (1, 1), 오른쪽 하단 (n, m).미로 속 의 모든 1×1 의 칸 은 장애 가 되 거나 비어 있다.
a 개의 로봇 이 미로 위 에서 미로 아래로 내 려 가 야 한다. 그 중에서 i 번 째 로봇 의 초기 위 치 는 (1, pi) 의 바로 위 이 고 (0, pi) 로 기억 해도 된다. 초기 운동 방향 은 아래로, 즉 (1, 0) 이다.
미로 에는 b 개의 출구 가 있 는데 그 중에서 i 번 째 출구 는 (n, ei) 의 바로 아래 에 있 으 니 (n + 1, ei) 로 기록 해도 무방 하 다.
지금 당신 은 이 로봇 들 을 미로 에서 벗 어 나 게 하려 고 합 니 다. 그러나 이 로봇 들 은 현재 의 운동 방향 만 따라 갈 뿐 커 브 를 돌 지 않 습 니 다. 그래서 미로 의 일부 빈 칸 에 커 브 장 치 를 설치 해 야 합 니 다. 각 칸 에 커 브 장치 만 있 을 수 있 습 니 다. 커 브 장 치 는 NW'', NE ', SW'', SE' 4 가지 가 있 습 니 다. 그 중에서:
'NW' 장 치 는 격자 위 에서 걸 어 오 는 로봇 의 운동 방향 을 왼쪽으로, 그리고 격자 왼쪽 에서 걸 어 오 는 로봇 의 운동 방향 을 위로, 로봇 이 격자 의 오른쪽 과 아래 에서 들 어 오 는 것 을 허락 하지 않 는 다.
'NE' 장 치 는 격자 위 에서 걸 어 오 는 로봇 의 운동 방향 을 오른쪽으로, 그리고 격자 오른쪽 에서 걸 어 오 는 로봇 의 운동 방향 을 위로, 로봇 이 격자 의 왼쪽 과 아래 에서 들 어 오 는 것 을 허락 하지 않 는 다.
'SW' 장 치 는 격자 아래 에서 걸 어 오 는 로봇 의 운동 방향 을 왼쪽으로 바 꾸 고, 격자 왼쪽 에서 걸 어 오 는 로봇 의 운동 방향 을 아래로 바 꾸 어 로봇 이 격자 의 오른쪽 과 위 에서 들 어 오 는 것 을 허락 하지 않 는 다.
'SE' 장 치 는 격자 아래 에서 걸 어 오 는 로봇 의 운동 방향 을 오른쪽으로, 그리고 격자 오른쪽 에서 걸 어 오 는 로봇 의 운동 방향 을 아래로, 로봇 이 격자 의 왼쪽 과 위 에서 들 어 오 는 것 을 허락 하지 않 는 다.
커 브 장 치 를 설치 하 는 방안 이 있 는 지 알 고 싶 습 니 다. 모든 로봇 이 장애 칸 을 거치 지 않 고 커 브 장치 에 불법 으로 들 어가 지 않 은 상태 에서 미 로 를 벗 어 날 수 있 도록 합 니 다 (여러 로봇 이 같은 칸 을 지나 도록 허용 합 니 다).에 너 지 는 출력 Yes''， No.
Input 은 첫 줄 의 정수 T 를 입력 하여 데이터 그룹 수 를 표시 합 니 다.
각 그룹의 데이터:
첫 번 째 줄 의 네 개의 정수 n, m, a, b 는 미궁의 크기, 로봇 개수, 출구 개 수 를 나타 낸다.
다음 n 줄 은 줄 마다 m 길이 의 01 문자열 si 로 미 로 를 표시 합 니 다. 그 중에서 i 번 째 문자열 의 j 번 째 문 자 는 미로 중 (i, j) 의 상 태 를 표시 합 니 다. 0 은 비어 있 고 1 은 장애 입 니 다.
다음 줄 a 는 서로 다른 정수 pi 로 로봇 의 초기 위치 (0, pi) 를 나타 낸다.
다음 줄 b 개의 서로 다른 정수 ei 는 출구 의 위치 (n + 1, ei) 를 나타 낸다.
1≤T≤10
1≤n,m≤100,1≤a,b,pi,ei≤m
출력 출력 은 총 T 줄 로 줄 당 하나의 문자열 Yes'' No '로 데이터 에 대한 답 을 표시 합 니 다.
Sample Input 2 3 4 2 2 0000 0011 0000 1 4 2 4 3 4 2 2 0000 0011 0000 3 4 2 4
Sample Output Yes No
뚜렷 한 최대 흐름 은 주로 어떻게 그림 을 만 드 는 것 입 니까?
우 리 는 모든 위치 에 커 브 장 치 를 놓 을 수 있다. 우 리 는 장 치 를 설치 한 곳 에서 두 개의 로봇 을 지나 갈 수 있 는 지 생각해 볼 수 있다.답 은 부정 적 이다.처음에는 로봇 이 모두 아래로 내 려 갔 고 같은 위치 에 로봇 이 하나 밖 에 없 었 기 때문에 같은 커 브 장치 에 도착 하려 면 커 브 를 거 쳤 을 것 이 분명 하지만 커 브 장 치 는 두 방향 으로 만 통행 할 수 있 기 때문에 부정 적 이다.
그래서 모든 로봇 은 계속 아래로 내 려 가 거나 모퉁이 를 돌 수 있다.즉, 점 을 상하 로 가 는 점 과 좌우 로 가 는 점 으로 나 누 면 유량 은 1 이 고 상하 로 가 는 점 과 좌우 로 가 는 점 사이 의 유량 은 1 이 며 대표 적 으로 한 번 돌 수 있 고 구체 적 으로 어떻게 돌아 도 된다.
그리고 최대 흐름 을 판단 하면 됩 니 다.
AC 코드:

#pragma GCC optimize(2)
#include
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=40010,M=1000010;
int T,n,m,a,b,h[N],s,t,base;
char g[110][110];
int head[N],nex[M],w[M],to[M],tot;
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
inline int id(int x,int y){
	return m*x+y;
}
inline int bfs(){
	memset(h,0,sizeof h);	h[s]=1;	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!h[to[i]]&&w[i]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(h[to[i]]==h[x]+1&&w[i]){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;	
}
signed main(){
	cin>>T;
	while(T--){
		tot=1;	memset(head,0,sizeof head);
		cin>>n>>m>>a>>b;	base=(n+2)*m;	t=base*2;
		for(int i=1;i<=n;i++)	scanf("%s",g[i]+1);
		for(int i=1;i<=a;i++){
			int x;	scanf("%d",&x);	g[0][x]='1';
			add(s,id(0,x),1);	add(id(0,x),id(1,x),1);
		}
		for(int i=1;i<=b;i++){
			int x;	scanf("%d",&x);	g[n+1][x]='1';
			add(id(n+1,x),t,inf);	add(id(n,x),id(n+1,x),inf);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(g[i][j]=='1')	continue;
				if(i-1>=1)	add(id(i,j),id(i-1,j),1);
				if(i+1<=n)	add(id(i,j),id(i+1,j),1);
				if(j-1>=1)	add(id(i,j)+base,id(i,j-1)+base,1);
				if(j+1<=m)	add(id(i,j)+base,id(i,j+1)+base,1);
				add(id(i,j),id(i,j)+base,1);	add(id(i,j)+base,id(i,j),1);
			}
		}
		puts(dinic()==a?"Yes":"No");
	}
	return 0;
}