Labyrinth

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<string> st;

vector<st> initst;
vector<st> states;

st init(int n, int m){
	st ret(n);
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			ret[i]+='1';
		}
	}
	return ret;
}

st rot(st x){
	int n=x.size();
	int m=x[0].size();
	st ret=init(m, n);
	for (int i=0;i<n;i++){
		for (int ii=0;ii<m;ii++){
			ret[ii][n-i-1]=x[i][ii];
		}
	}
	return ret;
}

st mir(st x){
	int n=x.size();
	int m=x[0].size();
	st ret=init(n, m);
	for (int i=0;i<n;i++){
		for (int ii=0;ii<m;ii++){
			ret[i][m-ii-1]=x[i][ii];
		}
	}
	return ret;
}

void print(st x){
	for (int j=0;j<(int)x.size();j++){
		for (int jj=0;jj<(int)x[j].size();jj++){
			cout<<x[j][jj];
		}
		cout<<endl;
	}
}

struct trf{
	int nstate;
	int dy,dx;
};

pair<st, pair<int, int> > minim(st x){
	int n=x.size();
	int m=x[0].size();
	int miy=n-1;
	int may=0;
	int mix=m-1;
	int maxx=0;
	for (int j=0;j<n;j++){
		for (int jj=0;jj<m;jj++){
			if (x[j][jj]=='0'){
				miy=min(miy, j);
				may=max(may, j);
				mix=min(mix, jj);
				maxx=max(maxx, jj);
			}
		}
	}
	assert(miy<=may&&mix<=maxx);
	st ret;
	for (int j=miy;j<=may;j++){
		string r;
		for (int jj=mix;jj<=maxx;jj++){
			r+=x[j][jj];
		}
		ret.push_back(r);
	}
	return {ret, {miy, mix}};
}

vector<trf> g[1010];

int startstate=-1;

string ma[50];

string lols[50];

int gn,gm;

int can(int y, int x, int s){
	if (y<0||x<0) return 0;
	if (y+(int)states[s].size()>gn) return 0;
	if (x+(int)states[s][0].size()>gm) return 0;
	for (int j=0;j<(int)states[s].size();j++){
		for (int jj=0;jj<(int)states[s][j].size();jj++){
			if (states[s][j][jj]=='0'&&ma[y+j][x+jj]=='1') return 0;
		}
	}
	return 1;
}

set<pair<pair<int, int>, int> > used;

int gy,gx,gs;
int fo=0;

void dfs(int y, int x, int s){
	if (fo) return;
	if (used.count({{y, x}, s})) return;
	used.insert({{y, x}, s});
	if (!can(y, x, s)) return;
	for (int i=0;i<gn;i++){
		lols[i]=ma[i];
	}
	for (int i=0;i<(int)states[s].size();i++){
		for (int ii=0;ii<(int)states[s][i].size();ii++){
			if (states[s][i][ii]=='0') lols[y+i][x+ii]='x';
		}
	}
	if (y==gy&&x==gx&&s==gs){
		fo=1;
		return;
	}
	for (auto nx:g[s]){
		dfs(y+nx.dy, x+nx.dx, nx.nstate);
	}
}

void solve(){
	for (int i=0;i<50;i++) ma[i].clear();
	int n,m;
	cin>>n>>m;
	gn=n;
	gm=m;
	int a,b;
	cin>>a>>b;
	for (int i=0;i<6;i++){
		for (int j=0;j<m;j++){
			ma[i]+='0';
		}
	}
	for (int i=6;i<n+6;i++){
		cin>>ma[i];
		assert((int)ma[i].size()==m);
	}
	for (int i=n+6;i<n+12;i++){
		for (int j=0;j<m;j++){
			ma[i]+='0';
		}
	}
	gy=n+6;
	gx=b-1;
	gs=startstate;
	n=n+12;
	gn=n;
	used.clear();
	fo=0;
	dfs(0, a-1, startstate);
	if (fo){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	initst.push_back({"00000"});
	initst.push_back({"000000"});
	initst.push_back({"0000000"});
	initst.push_back({"11110",
					  "00000"});
	initst.push_back({"11100",
		              "00000"});
	initst.push_back({"11100",
					  "00001"});
	initst.push_back({"11000",
		              "00001"});
	initst.push_back({"11000",
		              "00011"});
	initst.push_back({"111100",
		              "000001"});
	initst.push_back({"110000",
		              "000111"});
	initst.push_back({"11100",
		              "00001",
				      "01111"});
	initst.push_back({"11100",
		              "00001",
				      "00111"});
	initst.push_back({"11100",
		              "10001",
				      "00111"});
	initst.push_back({"11000",
		              "00011",
					  "01111"});
	initst.push_back({"11000",
		              "10011",
				      "00111"});
	initst.push_back({"11000",
		              "10001",
					  "00111"});
	initst.push_back({"1110",
		              "1100",
				      "1001",
				      "0011"});
	initst.push_back({"11100",
		              "11001",
				      "10011",
				      "00111"});
	initst.push_back({"1100",
		              "1100",
				      "1001",
				      "0011"});
	initst.push_back({"11000",
					  "00011",
				      "00111"});
	initst.push_back({"000000",
					  "111110"});
	initst.push_back({"00011",
		              "11001",
					  "11100",
					  "11110"});
	for (auto t:initst){
		auto nt=t;
		for (int i=0;i<4;i++){
			for (int j=0;j<2;j++){
				states.push_back(nt);
				nt=mir(nt);
			}
			nt=rot(nt);
		}
	}
	sort(states.begin(), states.end());
	states.erase(unique(states.begin(), states.end()), states.end());
	for (int i=0;i<(int)states.size();i++){
		if (states[i].size()==6&&states[i][0].size()==1){
			assert(startstate==-1);
			startstate=i;
		}
	}
	assert(startstate!=-1);
	for (int i=0;i<(int)states.size();i++){
		st t=states[i];
		int n=t.size();
		int m=t[0].size();
		for (int j=0;j<n;j++){
			for (int jj=0;jj<m;jj++){
				if (t[j][jj]=='0'){
					st nt=t;
					nt[j][jj]='1';
					auto lol=minim(nt);
					for (int ii=0;ii<(int)states.size();ii++){
						if (states[ii]==lol.F){
							g[i].push_back({ii, lol.S.F, lol.S.S});
							g[ii].push_back({i, -lol.S.F, -lol.S.S});
						}
					}
				}
			}
		}
	}
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER