牛客网 Wannafly挑战赛21 - B机器人

骑猪看日落 2022-05-17 05:17 175阅读 0赞

题目链接：[点我][Link 1]  
链接：https://www.nowcoder.com/acm/contest/159/B  
来源：牛客网

从前在月球上有一个机器人。  
月球可以看作一个 n\*m 的网格图，每个格子有三种可能：空地，障碍，机器人（有且仅有一个），现在地面指挥中心想让机器人在月球上行走，每次可以发送一个指令，为 U-往上走、D-往下走、L-往左走、R-往右走的其中之一。  
当机器人接收到一个行走指令时，如果即将到达的位置为障碍物，那么机器人将留在原地，否则机器人向对应方向走一步，如果其走出边界那么立即死亡。  
地面指挥中心当然不想让机器人就这么挂掉，因此其定义一个操作序列是安全的，当且仅当机器人按此操作序列走不会死亡。  
但是从地球向月球发信息不是个容易的事，而且有时候某些指令还会在茫茫宇宙中被吞没，比如指挥中心传出去 RUR 指令，到机器人那里就可能变成 RR 或者变成 U，因此定义一个操作序列是绝对安全的当且仅当其任意子序列都是安全的。  
现在地面指挥中心想知道，对于某一个地图，绝对安全的操作序列最长可以到多少，如果存在一个长度为正无穷的这样的序列，那么输出-1。  
**输入描述**:  
第一行一个正整数T，表示数据组数。  
接下来一共 T 组数据，每组数据第一行有两个正整数 n,m，表示网格图的大小, 接下来 n 行，每行 m 个字符，表示这张网格图。  
其中字符“.”表示空地，“\#”表示障碍物，“S”表示机器人所在位置。  
**输出描述:**  
一共 T 行，每行一个整数，表示答案。

**输入**

3
    5 5
    #####
    #...#
    .#S#.
    #...#
    #####
    1 7
    S......
    5 8
    #.######
    #.#..S.#
    #.#.##.#
    #......#
    ########

**输出**

-1
    6
    -1

数据范围 0≤T,n,m≤50

看上下左右有没有阻碍  
最大长度就是把上下左右最大可移动长度全部加上来

#include<iostream>
    using namespace std;
    int main(){
    	int t;
    	cin>>t;
    	int x,y;
    	char map[60][60];
    	while(t--){
    		int n,m;
    		cin>>n>>m;
    		for(int i=0;i<n;i++){
    			for(int j=0;j<m;j++){
    				cin>>map[i][j];
    				if(map[i][j]=='S'){
    					x=i;
    					y=j;
    				}
    			}
    		}
    		int flag=0;
    		for(int i=x+1;i<n;i++){
    			if(map[i][y]=='#'){
    				flag=1;break;
    			}
    		}
    		for(int i=0;i<x;i++){
    			if(map[i][y]=='#'){
    				flag=1;break;
    			}
    		}
    		for(int j=0;j<y;j++){
    			if(map[x][j]=='#'){
    				flag=1;break;
    			}
    		}
    		for(int j=y+1;j<m;j++){
    			if(map[x][j]=='#'){
    				flag=1;break;
    			}
    		}
    		if(flag){
    			cout<<-1<<endl;
    		}else{
    			cout<<n+m-2<<endl;
    		}
    	}
    }

[Link 1]: https://www.nowcoder.com/acm/contest/159/B