题目链接
https://loj.ac/problem/2733
题解
神仙题……
首先可以观察到一个结论: 目标块的两块小三明治一定分别是最后和倒数第二个被吃的。
由此我们可以考虑这两块谁先被吃。这样的好处就是，起初我们一个块被吃的依赖条件是某两个块中有一个被吃就行，现在两个块中的某一个已经钦定了比它更晚，另一个就一定要比它早，这样依赖关系就形成了一张图。
那么有一个\(O(n^4)\)的做法: 对于每一个块枚举先吃哪个小三明治，然后DFS求出要先吃这个三明治需要吃掉哪些三明治。
下面还有一个结论: 设对于一个块\((x,y)\) (第\(x\)行第\(y\)列)我们先吃掉了靠左边界的块，那么对于块\((x,y-1)\) (即它左边的块)，我们也需要先吃掉靠左边界的块，右同理。
推论: 设\(L(x,y)\)是要先取走块\((x,y)\)靠左边界的块需要取走的块的集合，则\(L(x-1,y)\subset L(x,y)\).
于是枚举每一行，在这一行中从左到右DFS求\(L\), 从右往左DFS求\(R\), 遍历过的点无需再遍历。
总时间复杂度\(O(n^3)\).
代码
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
using namespace std;const int N = 400;
const int INF = 1e8;
char a[N+3][N+3];
int vis[N+3][N+3];
int dp0[N+3][N+3],dp1[N+3][N+3];
int n,m;int dfs(int x,int y,int dir)
{if(vis[x][y]==-1) {return INF;}else if(vis[x][y]==1) {return 0;}vis[x][y] = -1; int ret = 2;if(a[x][y]=='N'){if(dir==1){if(x>1) {ret += dfs(x-1,y,a[x-1][y]=='N'?1:0);}if(y<m) {ret += dfs(x,y+1,1);}}else{if(x<n) {ret += dfs(x+1,y,a[x+1][y]=='N'?0:1);}if(y>1) {ret += dfs(x,y-1,0);}}}else{if(dir==1){if(x<n) {ret += dfs(x+1,y,a[x+1][y]=='N'?0:1);}if(y<m) {ret += dfs(x,y+1,1);}}else{if(x>1) {ret += dfs(x-1,y,a[x-1][y]=='N'?1:0);}if(y>1) {ret += dfs(x,y-1,0);}}}if(ret<INF) {vis[x][y] = 1;}else ret = INF;return ret;
}int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) scanf("%s",a[i]+1);for(int i=1; i<=n; i++){memset(vis,0,sizeof(vis));for(int j=1; j<=m; j++){dp0[i][j] = dp0[i][j-1]+dfs(i,j,0);if(dp0[i][j]>INF) {dp0[i][j] = INF;}}memset(vis,0,sizeof(vis));for(int j=m; j>=1; j--){dp1[i][j] = dp1[i][j+1]+dfs(i,j,1);if(dp1[i][j]>INF) {dp1[i][j] = INF;}}for(int j=1; j<=m; j++){int ans = min(dp0[i][j],dp1[i][j]);printf("%d ",ans<INF?ans:-1);}puts("");}return 0;
}
