「JOISC 2016 Day 2」三明治

「JOISC 2016 Day 2」三明治
这题真正让我感受了记搜的强大。
我真的没想过搜索可以过\(400\)的啊喂
对，\(\text{NOI}\)还可以过\(1e5\)呢

解法

一个并不显然的\(n^4\)的做法是枚举每一个点，然后上下左右记忆化搜索。考试的时候觉得难打，但是看完别人的代码之后发现还挺好打的。就是开一个变量看看当前需要释放哪里才可以释放自己就可以了。一个要注意的地方是，如果自己搜到了自己，那显然这种情况不成立，这块是吃不了的。
然后就想\(n^3\)的做法了。因为一个点要释放出来要不就是左边空了，要不就是右边空了。所以可以直接分别从左到右边搜一次，从右边到左边搜一次，信息可以重复利用因为之前的方块不成立当前就不成立，取之前的方块要吃的三明治这块也少不了。然后大力\(DFS\)就没了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
const int inf = 0x3f3f3f3f;
const int N = 400 + 10;

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
	for(; a >= '0' && a <= '9' ;a = getchar()) x = x * 10 + a - '0';
	return x * f;
}
int n,m;
char s[N][N];
int vis[N][N], f[N][N];
int tot;
inline void dfs(int x, int y, int op) {
	if(x < 1 || x > n || y < 1 || y > m || tot >= inf) return ;
	if(vis[x][y] == -1) { tot = inf; return ;}
	if(vis[x][y]) return ;
	tot += 2; vis[x][y] = -1;
	if(s[x][y] == 'N') {
		if(!op) dfs(x + 1, y, op ^ (s[x + 1][y] == 'Z')), dfs(x, y - 1, op);
		else dfs(x - 1, y, op ^ (s[x - 1][y] == 'Z')), dfs(x, y + 1, op);
	}
	else {
		if(!op) dfs(x - 1, y, op ^ (s[x - 1][y] == 'N')), dfs(x, y - 1, op);
		else dfs(x + 1, y, op ^ (s[x + 1][y] == 'N')), dfs(x, y + 1, op);
	}
	vis[x][y] = 1;
}

int main() {
	//freopen("sandwich.in","r",stdin);
//	freopen("sandwich.out","w",stdout);
	n = read(), m = read();
	for(R int i = 1; i <= n; i ++)	scanf("%s",s[i] + 1);
	memset(f, inf, sizeof(f));
	for(R int i = 1; i <= n; i ++) {
		memset(vis, 0, sizeof(vis)); tot = 0;
		for(R int j = 1; j <= m; j ++) {
			dfs(i, j, 0); f[i][j] = min(f[i][j], tot);
		}
		memset(vis, 0, sizeof(vis)); tot = 0;
		for(R int j = m; j >= 1; j --) {
			dfs(i, j, 1); f[i][j] = min(f[i][j], tot);
		}
	}
	for(R int i = 1; i <= n; i ++)
		for(R int j = 1; j <= m; j ++) {
			if(f[i][j] >= inf) f[i][j] = -1;
			printf("%d%c",f[i][j], j == m ? '\n' : ' ');
		}
	return 0;	
}