囧仙 的博客

囧仙 的博客

题解 P7262 【Get Your Wish】

posted on 2021-01-10 22:52:40 | under 题解 |

题目大意

  • 有一个 $n\times m$ 的矩阵,其中第 $(i,j)$ 个格子上是水滴、空格或者零件。现在所有水滴向同一个方向(上下左右)移动,询问水滴是否会碰到零件。

题解

显然,一个水滴只会关系到这一行/这一列(取决于流动方向)的零件的安危。对于不同的方向,我们只需要改变枚举顺序就行了。

现在假设一个水滴在第 $x$ 行/列上流动。我们只需要考虑它前面是否存在零件即可。也就是说,我们能够再次根据流动方向调整枚举顺序,用一个临时的布尔变量 $f$ 存储当前有没有碰到零件。枚举的时候有三种情况:

  • 遇到了空格,无事发生。

  • 遇到了零件。 $f\gets \verb!true!$ 。

  • 遇到了水滴。如果 $f=\verb!true!$ ,那么水滴会流经零件,直接输出 $\verb!GG!$ 并退出。否则水滴流走,无事发生。

顺便改变枚举顺序可能有点麻烦。但你可以根据流动方向旋转矩阵,这样只要处理一种枚举顺序了。但是由于作者太懒就没这么写。

参考代码

#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;
}