博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Round #234 (Div. 2) B. Inna and New Matrix of Candies
阅读量:5869 次
发布时间:2019-06-19

本文共 2551 字,大约阅读时间需要 8 分钟。

B. Inna and New Matrix of Candies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Inna likes sweets and a game called the "Candy Matrix". Today, she came up with the new game "Candy Matrix 2: Reload".

The field for the new game is a rectangle table of size n × m. Each line of the table contains one cell with a dwarf figurine, one cell with a candy, the other cells of the line are empty. The game lasts for several moves. During each move the player should choose all lines of the matrix where dwarf is not on the cell with candy and shout "Let's go!". After that, all the dwarves from the chosen lines start tosimultaneously move to the right. During each second, each dwarf goes to the adjacent cell that is located to the right of its current cell. The movement continues until one of the following events occurs:

  • some dwarf in one of the chosen lines is located in the rightmost cell of his row;
  • some dwarf in the chosen lines is located in the cell with the candy.

The point of the game is to transport all the dwarves to the candy cells.

Inna is fabulous, as she came up with such an interesting game. But what about you? Your task is to play this game optimally well. Specifically, you should say by the given game field what minimum number of moves the player needs to reach the goal of the game.

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000).

Next n lines each contain m characters — the game field for the "Candy Martix 2: Reload". Character "*" represents an empty cell of the field, character "G" represents a dwarf and character "S" represents a candy. The matrix doesn't contain other characters. It is guaranteed that each line contains exactly one character "G" and one character "S".

Output

In a single line print a single integer — either the minimum number of moves needed to achieve the aim of the game, or -1, if the aim cannot be achieved on the given game field.

Sample test(s)
input
3 4*G*SG**S*G*S
output
2
input
1 3S*G
output
-1
 
大意:

给n*m的方格,每行中都且仅有一个方格含S和G,每一步能够使全部的G向右移,仅仅到发生下列情况:1、某个G已到了最后一列。2、某个G已到了S。求把全部的G已到S须要的最少的步数。

解题思路:

统计不同的S-G差出现的个数。

#include
#include
#include
#define M 1005using namespace std;int main(){ char map[M][M]; int n,m,i,j,a[M],e,s; while(cin>>n>>m) { int a[M]; memset(a,0,sizeof(a)); int ans=0,k=0; for(i=0;i
>map[i]; /* for(i=0;i

转载地址:http://mvtnx.baihongyu.com/

你可能感兴趣的文章
初识DJango——Web框架
查看>>
php动态获取网页图片路径~
查看>>
28、可变参数和集合数组的互转
查看>>
[AX]AX2012 Form开发概览
查看>>
[AX]AX2012 Number sequence framework :(一)概览与原理浅析
查看>>
小程序单图上传到服务器
查看>>
iOS开发 - OC - 实现本地数据存储的几种方式一
查看>>
查看tomcat,jdk的操作位数
查看>>
C语言中的指针
查看>>
c51较c比较,单片机最小系统
查看>>
模式化窗口问题![window.dialogArguments]
查看>>
数据结构 - 二叉树(重构 + 遍历)
查看>>
四则运算程序
查看>>
手机端页面自适应解决方案
查看>>
15. 3Sum C++
查看>>
软件工程学概述(一)
查看>>
linux fdisk
查看>>
异或运算符使指定为翻转
查看>>
Eclipse Maven 构建(转)
查看>>
常用正则表达式积累
查看>>