Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct BCC {
- vector<vpi> adj; vpi ed;
- vector<vi> comps; // edges for each bcc
- int N, ti = 0; vi disc, st;
- void init(int _N) { N = _N; disc.rsz(N), adj.rsz(N); }
- void ae(int x, int y) {
- adj[x].eb(y,sz(ed)), adj[y].eb(x,sz(ed)), ed.eb(x,y); }
- int dfs(int x, int p = -1) { // return lowest disc
- int low = disc[x] = ++ti;
- trav(e,adj[x]) if (e.s != p) {
- if (!disc[e.f]) {
- st.pb(e.s); // disc[x] < LOW -> bridge
- int LOW = dfs(e.f,e.s); ckmin(low,LOW);
- if (disc[x] <= LOW) { // get edges in bcc
- comps.eb(); vi& tmp = comps.bk; // new bcc
- for (int y = -1; y != e.s; )
- tmp.pb(y = st.bk), st.pop_back();
- }
- } else if (disc[e.f] < disc[x]) // back-edge
- ckmin(low,disc[e.f]), st.pb(e.s);
- }
- return low;
- }
- void gen() { F0R(i,N) if (!disc[i]) dfs(i); }
- };
- BCC bcc;
- int n,m,q2, gr[MX], cnt;
- bool v[MX][MX][4], v2[MX][MX], grid[MX][MX];
- pi st,ed;
- int calc[MX*MX*2];
- int tr(int a, int b){return n*a+b;}
- int tr(int a, int b, int c){return (n*a+b)*4+c;}
- bool legal(int a, int b){return (a>=0 && b>=0);}
- void dumbdfs(int x, int y){
- For(i,4){
- int nx=x+xd[i],ny=y+yd[i];
- if(nx==ed.f && ny==ed.s)continue;
- if(legal(nx,ny) && grid[nx][ny] && !v2[nx][ny]){
- v2[nx][ny]=1;
- dumbdfs(nx,ny);
- }
- }
- }
- int main() {
- setIO();
- re(n,m,q2);
- bcc.init(2*MX*MX);
- For(i,n){
- string s;re(s);
- For(j,m){
- grid[i][j]= (s[j]=='.' || s[j]=='A' || s[j]=='B');
- if(s[j]=='A')st=mp(i,j);
- if(s[j]=='B')ed=mp(i,j);
- }
- }
- For(i,n)For(j,m){if(!grid[i][j])continue;
- if(grid[i+1][j]){
- bcc.ae(tr(i,j),tr(i+1,j));
- calc[tr(i,j,2)]=cnt;
- calc[tr(i+1,j,0)]=cnt;
- cnt++;
- }
- if(grid[i][j+1]){//careful here
- bcc.ae(tr(i,j),tr(i,j+1));
- calc[tr(i,j,3)]=cnt;
- calc[tr(i,j+1,1)]=cnt;//nums
- cnt++;
- }
- }
- bcc.gen();
- For(i,sz(bcc.comps)){
- trav(x,bcc.comps[i])gr[x]=i+1;
- }
- dumbdfs(st.f,st.s);
- queue<pii> q;
- For(i,4){
- int nx=ed.f+xd[i], ny=ed.s+yd[i];
- int tx=ed.f, ty=ed.s;
- if(legal(nx,ny) && v2[nx][ny]){
- q.push(mp(mp(tx,ty),(i+2)%4));
- v[tx][ty][(i+2)%4]=1;
- }
- }
- while(!q.empty()){
- pii x=q.front();q.pop();
- int ox=x.f.f+xd[x.s], oy=x.f.s+yd[x.s];
- // dbg(x,ox,oy,legal(ox,oy),grid[ox][oy],v[ox][oy][x.s]);
- if(legal(ox,oy) && grid[ox][oy] && !v[ox][oy][x.s]){
- v[ox][oy][x.s]=1;
- q.push(mp(mp(ox,oy),x.s));
- }
- For(i,4){
- int nx=x.f.f, ny=x.f.s;
- if(!v[nx][ny][i] && gr[calc[tr(nx,ny,x.s)]]==gr[calc[tr(nx,ny,i)]]){
- // if(nx==2 && ny==2 && i==2)dbg("hi",nx,ny,x,i,calc[tr(nx,ny,x.s)],calc[tr(nx,ny,i)] );
- v[nx][ny][i]=1;
- q.push(mp(mp(nx,ny),i));
- }
- }
- }
- For(i,q2){
- int a, b;re(a,b);a--;b--;
- ps((v[a][b][0]||v[a][b][1]||v[a][b][2]||v[a][b][3])?"YES":"NO");
- }
- dbg(bcc.comps);
- // you should actually read the stuff at the bottom
- }
Add Comment
Please, Sign In to add comment