Jerrlee's blog

Jerrlee's blog

CF1680B 题解

posted on 2022-05-15 14:23:34 | under 题解 |

题意

$t$ 组数据,每组数据给定 $n$ 和 $m$ 和 $n \times m$ 的矩形。

矩形中的 R 代表机器人,E 代表空地。每次操作可以使所有机器人向上或下或左或右移动一格。问能否在所有机器人不出格的情况下使其中一个机器人达到左上角。

思路

既然要到左上角,那就可以只向上或左移动。

反过来思考,怎样会使机器人出格?

  • 向左时出格,那就不向左,向上;

  • 向上时出格,那就不向上,向左。

那么,如果以上两种情况,无论如何移动都会导致机器人出格,肯定是类似如下图的情况:

ERE
REE

这类情况,必定是最左边的机器人上方还有机器人,或者说最上面的机器人左边还有机器人。

反过来,只要所有机器人横纵坐标最小值的位置有机器人,那说明可以满足题意,反之则不能。

代码

#include<iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int mx=n,mn=m;
        char x[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>x[i][j];
                if(x[i][j]=='R'){
                    mx=min(mx,i);
                    mn=min(mn,j);
                }
            }
        }
        if(x[mx][mn]=='R') cout<<"YES\n";
        else cout<<"NO\n";
    }
}

AC 记录(洛谷)

AC 记录(CF)