【ZCMU1434】糖果迷阵

题目链接

1434: 糖果迷阵

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 93  Solved: 44
[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); 输入

 

Source

 

解题思路：

乍一看还以为是到模拟题，但实际上比想象的要简单qaq

先判断一下是否可以完成游戏，只要当每一行的G在S之即可完成游戏，反之有一行不满足则不能完成。

然后只需计算每一行的G和S之差记录到数组中进行排序，因为当一些侏儒到达糖果所在单元格获得糖果时一轮就结束了，所以只需要每次取出数组中最小的数，将其标为0表示已经获得糖果，其他数减去这个最小的数即代表他们在这一轮中移动的位置，再次排序，进行上述操作，当数组中的元素全为不大于0的数时表示游戏结束，输出答案。

 

代码：

#include<bits/stdc++.h> using namespace std; int a[1005],n,m; int judge() {for(int i=0;i<n;i++){if(a[i]>0)return 1;}return 0; } int main() {while(~scanf("%d%d",&n,&m)){char s[n][m];int flag=0,ans=0,k=0,i,j;for(i=0;i<n;i++)scanf("%s",s[i]);for(i=0;i<n;i++){int x,y;for(j=0;j<m;j++){if(s[i][j]=='G')x=j;if(s[i][j]=='S')y=j;}if(y<x)flag=1;else a[k++]=y-x;}if(flag)printf("-1\n");else{while(judge()){sort(a,a+k);for(i=0;a[i]<=0;i++);int x=a[i];for(j=0;j<n;j++)a[j]=a[j]-x; ans++;//for(i=0;i<n;i++)cout<<a[i]<<" ";//cout<<endl; } printf("%d\n",ans); }}return 0; }

 

总结

以上是生活随笔为你收集整理的【ZCMU1434】糖果迷阵的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。