題目連結:點我 連結: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
#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;
}
}
}