题解 [email protected]洛谷 【Get Your Wish】

题意很清楚了这里就不过多解释了,说一下思路:

一看题,感觉很多水滴的时候较难模拟下落过程,因此考虑根据给出的重力方向和电子元件反推。我们使用 si,js_{i,j} 表示如果 (i,j)\left(i,j\right) 位置有水滴,是否会影响到电子元件。则以方向竖直向下为例,si,j=si,j+1(当前位置有水滴)s_{i,j}=s_{i,j+1}|\left(\text{当前位置有水滴}\right),其他三个方向以此类推,其中 | 表示或,即两个条件中任一满足则为 11

然后枚举整个 n×mn\times m 的图:如果存在水滴使对应位置的 si,j=1s_{i,j}=1,则答案必定为 GG;若对于所有水滴对应位置的 si,js_{i,j} 均为 00,则答案为 OK

赛时代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 105;
//const char nxt[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, m, pos, s[N][N], ans = 0;
char mp[N][N], poss[N];

int main() {
	scanf("%d%d%s", &n, &m, poss+1);
	rep(i, 1, n) scanf("%s", mp[i]+1);
	pos = (poss[1] == 'v' ? 1 : (poss[1] == '<' ? 2 : (poss[1] == '^' ? 3 : 0)));
	if(!pos) rep(i, 1, n) per(j, m, 1) s[i][j] = s[i][j+1] | (mp[i][j] == 'x');
	else if(pos == 1) rep(j, 1, m) per(i, n, 1) s[i][j] = s[i+1][j] | (mp[i][j] == 'x');
	else if(pos == 2) rep(i, 1, n) rep(j, 1, m) s[i][j] = s[i][j-1] | (mp[i][j] == 'x');
	else rep(j, 1, m) rep(i, 1, n) s[i][j] = s[i-1][j] | (mp[i][j] == 'x');
	rep(i, 1, n) rep(j, 1, m) ans |= (s[i][j] && (mp[i][j] == 'o'));
	printf("%s\n", (char*[]){"OK", "GG"}[ans]);
    return 0;
}