ZCMU—1434

1434: 糖果迷陣

Time Limit: 1 Sec  Memory Limit: 128 MB

[​​Submit​​​][​​Status​​​][​​Web Board​​]

Description

Inna 喜歡吃糖和遊戲糖果迷陣.今天，他推出了新遊戲“糖果迷陣2：重新整理”。

遊戲由一個nxm的矩陣表組成。矩陣每行包含一個帶有侏儒的單元格和一塊帶有糖果的單元格，和一些空的單元格。遊戲有多次操作，每次操作玩家需要選中所有那些侏儒沒獲得糖果的行，并發出指令“Let’s go!”.之後所有選中行的侏儒開始同時向右移動，每秒每個侏儒隻能向目前單元格的右側相鄰單元格移動一格，操作一直持續到發生以下事件之一時：

·一些侏儒到達所在行的最右邊

·一些侏儒到達糖果所在單元格獲得糖果

當所有侏儒得到糖果時結束

Inna是如此聰明得設計出這個遊戲. 可是你們呢? 你的任務是用最優的方法來完成這個遊戲，也就是用最少的操作來完成這個遊戲。

Input

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

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

Output

在一行列印單個整數 - 來表示完成遊戲的最優解，或-1如果目标不能在給定的遊戲場中可以實作所需的運動或最小數目。

Sample Input

3 4

*G*S

G**S

*G*S

1 3

S*G

Sample Output

2

-1

HINT

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

【分析】

水題...題目寫的好像是bfs啊dp啊什麼什麼的都是逗你的...

每次可以選擇很多行一起向右，直到其中某一行的G碰到S就停止這次操作...那麼顯然...相同距離的行隻需要一次操作，不同距離的行...有幾個不同的距離就需要幾次..是以就是找每行G和S的距離有幾種就可以了...

然後-1的情況就是S在G左邊..

【代碼】

#include <stdio.h>
#include <string.h>
int main()
{
  int n,m;
  int f[2000];
  char s[10000];
  while (~scanf("%d%d",&n,&m))
  {
    memset(f,0,sizeof(f));
    int t=1;
    int ans=0;
    int j,x;
    for (int i=0;i<n;i++)
    {
      scanf("%s",s);
      if (t)
      {
        j=x=0;
        while (s[j]!='G') 
        {
          if (s[j]=='S') t=0;
          j++;
        }
        while (s[j+x]!='S' && t) x++;
        f[x]++;
        if (f[x]==1) ans++;
      }
    }
    if (!t) printf("-1\n");
    else printf("%d\n",ans);
  }
}