Description

Input

輸入的第一行包含兩個(gè)整數(shù)n和m（1≤N≤1000;2≤M≤1000）。

每個(gè)接下來的n行包含m個(gè)字符 – 代表這局的“糖果迷陣：刷新”。字符“*”表示該領(lǐng)域的空白單元格，字符“G”代表一個(gè)侏儒和字符“S”代表一個(gè)糖果。矩陣不包含其他字符。這是保證每行包含一個(gè)字符“G”和一個(gè)字符“S”。

Output

在一行打印單個(gè)整數(shù) - 來表示完成游戲的最優(yōu)解，或-1如果目標(biāo)不能在給定的游戲場中可以實(shí)現(xiàn)所需的運(yùn)動或最小數(shù)目。

Sample Input

Sample Output

HINT

 請使用cin>>str; 或者scanf("%s",str); 輸入

【解析】

這道題其實(shí)很坑，然人覺得是和圖有關(guān)要dfs或者bfs，其實(shí)吧這個(gè)其實(shí)沒有那么難，意思就是G是侏儒，S是糖果在的地方，我們可以讓侏儒一起向右走，問什么時(shí)候可以讓所有的侏儒都找到糖果，那其實(shí)就是算G和S中間有幾個(gè)不同的位置，比如樣例1總共有兩個(gè)不同的中間隔著的。比如說第一行和第三行中間都只隔了一個(gè)，而第二行隔了2個(gè)，所有總共是兩個(gè)不同就輸出2。

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int main(){    char s[10020];    int a[1002];    int i,n,m,j,flag,k,flag1,count1;    while(~scanf("%d%d",&n,&m))    {        flag1=0;        count1=0;        memset(a,0,sizeof(a));        for(i=0;i<n;i++)        {            scanf("%s",s);            k=0;            j=0;            flag=0;            while(s[j]!='S')            {                if(s[j]=='G')                {                    flag=1;                }                else if(flag==1)                {                    k++;                }                j++;            }            a[k]++;            if(a[k]==1)                count1++;            if(flag==0)            {                flag1=1;            }        }        if(flag1==1)            PRintf("-1/n");        else            printf("%d/n",count1);    }    return 0;}