题目
题目描述
农夫john最近在研究如果发生重大事故，如何让农场里的奶牛逃离问题。他想要确信在紧急情况下，所有的奶牛都有一个安全逃离方案。因为在紧急情况下，奶牛们都会失去观察和判断能力，所以最近john一直在教奶牛们逃离的方法，他的方法很简单，就是任何时候都只向北方或东方逃离，北方是行坐标减1的方向，东方是列坐标加1的方向。奶牛们虽笨，不过这一点事关自己的生命，所以他们牢记在心，而且也一定会这么做。
当然也会出问题，奶牛们在逃离的方向上会横冲直撞，为了阻止奶牛之间互相冲撞造成伤害，john要求任何一个奶牛的逃离路线不能经过其它奶牛的初始位置。一个逃离方案是安全的如果它能够满足上面的要求，反之它就是不安全的。
奶牛们所在的土地（农场）被划分成了rr行和cc列的一个矩形地图。奶牛们都待在这个矩形中的某一个位置。
请帮助john确定给定的一个地图上是否存在一个安全的逃离方案。
比如，下面的两个图：
左边的例子表示了一个能够安全逃离的地图，因为没有任何一个奶牛的逃离路线上包括其他奶牛。右边的例子表示了一个不安全的地图，因为位于(4,1)(4,1)的奶牛不论是向东逃离还是向北逃离，它的路线上都会有别的奶牛，从这个图中拿掉任意一头奶牛，这个地图都会变成安全的。
输入输出格式
输入格式
第$1$行：两个整数$r,c$，用1个空格隔开，表示矩形的行数和列数（均 $\le 50$）。
第$2$行：一个整数$n$，表示奶牛的个数（$\le 100$）。
第$3$到$n+2$行：共$n$行，每行有$2$个整数，之间用$1$个空格隔开，分别表示这头奶牛所在的行和列。
每输入完一行后，会输入多余的字符！！！
输出格式
如果这块土地是安全的，输出$0$。
如果移走任意一头奶牛这块土地还是不安全，输出$-1$。否则输出移走的那头奶牛的编号，如果有多个奶牛满足要求，输出所有的数。
输入输出样例
输入样例
5 5
5
1 1
2 4
3 1
2 2
2 1
输出样例
1
5
题解
这一题的题目有问题（我在百度上查了，所有题目都是错的。多亏了洛谷的在线测评，把题解复制在上面执行，就可以知道题目错误了）。我整整研究了一天才研究出来。最后，我是在另一个人提交的AC程序上找出了我的错误。这个错误你根本是不可能想到的（虽然我不知道以前的人是怎么发现的），这个错误是就是我在题目中加粗的字其实这个问题我在一个OJ上也有注意到（那个OJ可以下载不完整的数据），但是我并不知道这是一个漏洞。
这道题的思路就是模拟，首先遍历所有的奶牛，若全部安全，则输出0，结束。如果不是全部安全的，则每次将一只奶牛删除，再遍历全部，看看是否全是安全的，如果是，则输出该奶牛编号，直到所有情况都遍历完了，再讨论-1的情况。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
int m[51][51],h,l,n;
struct cow{ //结构体，也可以用x[101]和y[101]
int x,y;
};
cow a[101];
int anquan(int x,int y){ //每头奶牛安全的条件
int t1=1,t2=1;
for(int i=1;i<x;i++) if(m[i][y]) {t1=0;break;} //如果北面有奶牛，那么t1=0
for(int i=y+1;i<=l;i++) if(m[x][i]) {t2=0;break;} //如果东面有奶牛，那么t2=0
if(t1==0&&t2==0) return 0; else return 1; //如果两边都有奶牛，则不安全，反之安全
}
int qaq(){ //所有奶牛都安全
for(int i=1;i<=h;i++) for(int j=1;j<=l;j++) if(m[i][j]) if(!(anquan(i,j))) return 0; //遍历整个农场，如果有奶牛不安全，那么返回0
return 1; //否则返回1
}
int aq(int x,int y){ //去掉一只奶牛后安全
m[x][y]=0; //删除奶牛
return qaq();
}
int main()
{
int temp=0;
char s[100];
cin>>h>>l>>n;
memset(a,0,sizeof(a));memset(m,0,sizeof(m)); //初始化
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y; //输入
m[a[i].x][a[i].y]=i; //也可以赋值为1
gets(s);
}
if(qaq()) {cout<<0;return 0;} //如果全部安全，输出0，结束
for(int i=1;i<=n;i++){
if(aq(a[i].x,a[i].y)) /*如果去掉后安全*/if(!temp) /*如果是第一次输出*/cout<<i,temp++; else cout<<endl<<i;
m[a[i].x][a[i].y]=i; //这步非常重要，不然第二次执行的时候就删除了两只奶牛
}
if(!temp) cout<<-1; //如果删掉任何一只奶牛都不安全，输出-1
return 0;
}