haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

信息竞赛题8

发布时间:2013-12-18 11:38:19  

安全逃离

农夫john最近在研究如果发生重大事故,如何让农场里的奶牛逃离问题。他想要确信在紧急情况下,所有的奶牛都有一个安全逃离方案。因为在紧急情况下,奶牛们都会失去观察和判断能力,所以最近john一直在教奶牛们逃离的方法,他的方法很简单,就是任何时候都只向北方或东方逃离,北方是行坐标减1的方向,东方是列坐标加1的方向。奶牛们虽笨,不过这一点事关自己的生命,所以他们牢记在心,而且也一定会这么做。

当然也会出问题,奶牛们在逃离的方向上会横冲直撞,为了阻止奶牛之间互相冲撞造成伤害,john要求任何一个奶牛的逃离路线不能经过其它奶牛的初始位置。一个逃离方案是安全的如果它能够满足上面的要求,反之它就是不安全的。

奶牛们所在的土地(农场)被划分成了r行和c列的一个矩形地图。奶牛们都待在这个矩形中的某一个位置。

请帮助john确定给定的一个地图上是否存在一个安全的逃离方案。

比如,下面的两个图:

左边的例子表示了一个能够安全逃离的地图,因为没有任何一个奶牛的逃离路线上包括其他奶牛。右边的例子表示了一个不安全的地图,因为位于(4,1)的奶牛不论是向东逃离还是向北逃离,它的路线上都会有别的奶牛,从这个图中拿掉任意一头奶牛,这个地图都会变成安全的。

安全 不安全

| | | | C-- C . . . . .

| | | | C-- ^ . . . . .

| C | | C-- | . . . . .

C C-+-+---- C------>C .

. . C C C-- . . . . . .

C表示奶牛,直线表示逃离路线

输入evac.in

第1行:两个整数r,c,用1个空格隔开,表示矩形的行数和列数(均不超过50)。 第2行:一个整数n,表示奶牛的个数(不超过100)。

第3到n+2行:共n行,每行有两个整数,之间用1个空格隔开,分别表示这头奶牛所在的行和列。

输出evac.out

如果这块土地是安全的,输出0。

如果移走任意一头奶牛这块土地还是不安全,输出-1。

否则输出1,并且在下一行输出移走的那头奶牛的编号,如果有多个奶牛满足要求,输出输入序列中编号最小一个。

样例: evac.in

5 5

5

1 1

2 4

3 1

2 2

2 1

evac.out

1

1

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com