HNU练习七字符串编程题7. 机器人游戏

本文介绍: 有人建造了一些机器人，并且将他们放置在包含n个单元的一维网格上，一个长度为n的字符串 s 代表了他们的编排方式，字符串中的字符既可以是’.’，也可以是’0’~’9’之间的一个数字字符，字符‘.’表示开始时在相应的单元上无机器人，数字表示开始时在相应的单元上有一个机器人。例如，假定字符串的第7个字符为3，代表机器人从第7个单元开始，他的活动范围为第4个单元（7-3=4）到第10个单元（7+3=10）(包含两个端点），机器人仅仅可以在这个范围内移动，但不可以移出网格。请判断，机器人的编排方式是否安全。

【问题描述】

有人建造了一些机器人，并且将他们放置在包含n个单元的一维网格上，一个长度为n的字符串 s 代表了他们的编排方式，字符串中的字符既可以是’.’，也可以是’0’~’9’之间的一个数字字符，字符‘.’表示开始时在相应的单元上无机器人，数字表示开始时在相应的单元上有一个机器人。特别地，数字x 表示他可以从开始点向左移动 x个单元，或从开始点向右移动x个单元，每次移动距离为一个单元格。

例如，假定字符串的第7个字符为3，代表机器人从第7个单元开始，他的活动范围为第4个单元（7-3=4）到第10个单元（7+3=10）(包含两个端点），机器人仅仅可以在这个范围内移动，但不可以移出网格。一旦达到范围边界，机器人会折返。

在此范围内，开始时机器人可以在任意时间按照任意方向移动，但如果两个机器人可能同时到达同一单元格时，就会发生碰撞。

请判断，机器人的编排方式是否安全。

【输入形式】

4
....
.2.....
.2...2..
1.1.1.

safe
safe
unsafe
unsafe

#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include<cmath>
using namespace std;
int main()
{
	int t,l,m[10000];
	string s;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		memset(m,0,sizeof(m));
		cin>>s;
		l=s.length();
		for(int j=0;j<l;j++)
		{
			if(s[j]<='9'&amp;&amp;s[j]>='0')
			{
				for(int k=max(0,j-s[j]+'0');k<=min(j+s[j]-'0',l);k++)
				{
					m[k]++;
				}
			}
		}
		int flag=0;
		for(int j=0;j<l;j++)
		{
			if(m[j]>1) 
			{
				flag=1;
				cout<<"unsafe"<<endl;
				break;
			}
		}
		if(flag==0) cout<<"safe"<<endl;
	}
}