【Codeforces 1205C】Palindromic Paths（回文路径DP）

题目链接对于格子( i , j ) (i,j)(i,j)若i j ijij为奇数则称为奇点否则称为偶点。首先发现询问距离为2的两个格子就可以知道它们是否值相同。已知( 1 , 1 ) (1,1)(1,1)格子值为1( n , n ) (n,n)(n,n)格子值为0一遍BFS可以求出所有偶点的值。如果( 1 , 2 ) (1,2)(1,2)格子的值已知那么再一遍BFS可以求出所有奇点的值。我们假设( 1 , 2 ) (1,2)(1,2)格子值为0/1得到两种结果。因题目保证有解所以两种结果下必然存在一组合法询问的答案不同我们得到这组询问的答案就知道哪种结果正确了。我们用DP分别求出两种结果下所有询问的答案即可。设S [ x 1 ] [ y 1 ] [ x 2 ] [ y 2 ] S[x1][y1][x2][y2]S[x1][y1][x2][y2]表示( x 1 , y 1 ) (x1,y1)(x1,y1)与( x 2 , y 2 ) (x2,y2)(x2,y2)之间是否有合法回文路径它为YES的条件是( x 1 , y 1 ) (x1,y1)(x1,y1)和( x 2 , y 2 ) (x2,y2)(x2,y2)两个格子的值相同且它们之间存在合法路径并满足( x 1 , y 1 ) (x1,y1)(x1,y1)与( x 2 , y 2 ) (x2,y2)(x2,y2)相同或接壤或者存在( x 1 ′ , y 1 ′ ) (x1,y1)(x1′,y1′)( x 2 ′ , y 2 ′ ) (x2,y2)(x2′,y2′)满足( x 1 ′ , y 1 ′ ) (x1,y1)(x1′,y1′)是( x 1 , y 1 ) (x1,y1)(x1,y1)路径的后继( x 2 ′ , y 2 ′ ) (x2,y2)(x2′,y2′)是( x 2 , y 2 ) (x2,y2)(x2,y2)路径的前驱且S [ x 1 ′ ] [ y 1 ′ ] [ x 2 ′ ] [ y 2 ′ ] S[x1][y1][x2][y2]S[x1′][y1′][x2′][y2′]为YES。用记忆化搜索写起来会方便些复杂度为O ( n 4 ) O(n^4)O(n4)。在两遍BFS中一共用到了n 2 − 3 n^2-3n2−3个询问最后用到了一个询问询问总数为n 2 − 2 n^2-2n2−2符合题意。#includestdio.h#includealgorithm#includeiostream#includequeue#includecmath#includestring.h#includeset#defineLL long longusingnamespacestd;LLread(){LL sum0;charcgetchar();boolf0;while(c0||c9){if(c-)f1;cgetchar();}while(c0c9){sumsum*10c-0;cgetchar();}if(f)return-sum;returnsum;}intn;constintdx[]{2,1,1,0,0,-1,-1,-2};constintdy[]{0,1,-1,2,-2,1,-1,0};constintDX[]{0,1,-1,0};constintDY[]{1,0,0,-1};#defineCI const intboolCH(intx1,inty1,intx2,inty2){if(x1x2y1y2)return1;swap(x1,x2);swap(y1,y2);return(x1x2y1y2);}boolASK(CIx1,CIy1,CIx2,CIy2){printf(? %d %d %d %d\n,x1,y1,x2,y2);fflush(stdout);returnread()^1;}intqx[2505],qy[2505];structEX{boolS[55][55],vis[55][55];boolF[55][55][55][55],V[55][55][55][55];voidBFS(boolT){inth,t,i,x,y,x1,y1,x2,y2,rx,ry;if(!T){h1;t2;qx[1]1;qy[1]1;S[1][1]1;vis[1][1]1;qx[2]n;qy[2]n;S[n][n]0;vis[n][n]1;}else{ht1;qx[1]1;qy[1]2;S[1][2]0;vis[1][2]1;}while(ht){xqx[h];yqy[h];h;for(i0;i8;i){x1x;y1y;x2x1dx[i];y2y1dy[i];if(x21||x2n||y21||y2n||vis[x2][y2])continue;if(CH(x1,y1,x2,y2)){if(xx2yy2)rxx1,ryy1;elserxx2,ryy2;vis[rx][ry]1,S[rx][ry]S[x][y]^ASK(x1,y1,x2,y2),qx[t]rx,qy[t]ry;}}}}boolDFS(intx1,inty1,intx2,inty2){if(V[x1][y1][x2][y2])returnF[x1][y1][x2][y2];V[x1][y1][x2][y2]1;if(S[x1][y1]!S[x2][y2])returnF[x1][y1][x2][y2]0;if(abs(x1-x2)abs(y1-y2)1)returnF[x1][y1][x2][y2]1;inti,j,X1,Y1,X2,Y2;for(i0;i2;i){X1x1DX[i];Y1y1DY[i];if(X11||X1n||Y11||Y1n)continue;for(j2;j4;j){X2x2DX[j];Y2y2DY[j];if(X21X2nY11Y2nCH(X1,Y1,X2,Y2)DFS(X1,Y1,X2,Y2))returnF[x1][y1][x2][y2]1;}}returnF[x1][y1][x2][y2]0;}voidoutput(){puts(!);for(inti1;in;i){for(intj1;jn;j)printf(%d,S[i][j]);puts();}}}K1,K2;intmain(){nread();K1.BFS(0);K1.BFS(1);inti,j,k,t,x1,y1,x2,y2;for(inti1;in;i)for(intj1;jn;j)K2.S[i][j]K1.S[i][j]^((ij)1);for(i1;in;i)for(j1;jn;j)for(k1;kn;k)for(t1;tn;t){x1i;y1j;x2k;y2t;if(!CH(x1,y1,x2,y2))continue;K1.DFS(x1,y1,x2,y2),K2.DFS(x1,y1,x2,y2);if(K1.F[x1][y1][x2][y2]K2.F[x1][y1][x2][y2])continue;if(abs(x1-x2)abs(y1-y2)1)continue;if(ASK(x1,y1,x2,y2)K1.F[x1][y1][x2][y2])K2.output();elseK1.output();return0;}return0;}