题解 P7262 【Get Your Wish】

囧仙

2021-01-10 22:52:40

Solution

## 题目大意 - 有一个 $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; } ```