题解 P7262 【Get Your Wish】
囧仙
2021-01-10 22:52:40
## 题目大意
- 有一个 $n\times m$ 的矩阵,其中第 $(i,j)$ 个格子上是水滴、空格或者零件。现在所有水滴向同一个方向(上下左右)移动,询问水滴是否会碰到零件。
## 题解
显然,一个水滴只会关系到这一行/这一列(取决于流动方向)的零件的安危。对于不同的方向,我们只需要改变枚举顺序就行了。
现在假设一个水滴在第 $x$ 行/列上流动。我们只需要考虑它前面是否存在零件即可。也就是说,我们能够再次根据流动方向调整枚举顺序,用一个临时的布尔变量 $f$ 存储当前有没有碰到零件。枚举的时候有三种情况:
- 遇到了空格,无事发生。
- 遇到了零件。 $f\gets \verb!true!$ 。
- 遇到了水滴。如果 $f=\verb!true!$ ,那么水滴会流经零件,直接输出 $\verb!GG!$ 并退出。否则水滴流走,无事发生。
顺便改变枚举顺序可能有点麻烦。但你可以根据流动方向旋转矩阵,这样只要处理一种枚举顺序了。~~但是由于作者太懒就没这么写。~~
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=100+3;
int qread(){
int w=1,c,ret;
while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*w;
}
char rdc(){
char c; while(!isgraph(c=getchar())); return c;
}
int n,m,t; char W[MAXN][MAXN];
int main(){
n=qread(),m=qread(),t=rdc(),t=(t=='^'?1:t=='v'?2:t=='<'?3:4);
up(1,n,i) up(1,m,j) W[i][j]=rdc();
if(t<=2){
up(1,m,i){
bool f=0;
if(t==2){ up(1,n,j) if(f&&W[j][i]=='x') goto nxt; else if(W[j][i]=='o') f=true;}
if(t==1){ dn(n,1,j) if(f&&W[j][i]=='x') goto nxt; else if(W[j][i]=='o') f=true;}
}
} else {
up(1,n,i){
bool f=0;
if(t==4){ up(1,m,j) if(f&&W[i][j]=='x') goto nxt; else if(W[i][j]=='o') f=true;}
if(t==3){ dn(m,1,j) if(f&&W[i][j]=='x') goto nxt; else if(W[i][j]=='o') f=true;}
}
}
puts("OK");return 0; nxt: puts("GG");
return 0;
}
```