2266 - 安全逃离
农夫john最近在研究如果发生重大事故，如何让农场里的奶牛逃离问题。他想要确信在紧急情况下，所有的奶牛都有一个安全逃离方案。因为在紧急情况下，奶牛们都会失去观察和判断能力，所以最近john一直在教奶牛们逃离的方法，他的方法很简单，就是任何时候都只向北方或东方逃离，北方是行坐标减1的方向，东方是列坐标加1的方向。奶牛们虽笨，不过这一点事关自己的生命，所以他们牢记在心，而且也一定会这么做。
当然也会出问题，奶牛们在逃离的方向上会横冲直撞，为了阻止奶牛之间互相冲撞造成伤害，john要求任何一个奶牛的逃离路线不能经过其它奶牛的初始位置。一个逃离方案是安全的如果它能够满足上面的要求，反之它就是不安全的。
奶牛们所在的土地（农场）被划分成了r行和c列的一个矩形地图。奶牛们都待在这个矩形中的某一个位置。
请帮助john确定给定的一个地图上是否存在一个安全的逃离方案。
比如，下面的两个图：
左边的例子表示了一个能够安全逃离的地图，因为没有任何一个奶牛的逃离路线上包括其他奶牛。右边的例子表示了一个不安全的地图，因为位于(4,1)的奶牛不论是向东逃离还是向北逃离，它的路线上都会有别的奶牛，从这个图中拿掉任意一头奶牛，这个地图都会变成安全的。
安全 不安全
| | | | C-- C . . . . .
| | | | C-- ^ . . . . .
| C | | C-- | . . . . .
C C-+-+---- C------>C .
. . C C C-- . . . . . .
C表示奶牛，直线表示逃离路线
Input
第1行：两个整数r,c，用1个空格隔开，表示矩形的行数和列数（均不超过50）。
第2行：一个整数n，表示奶牛的个数（不超过100）。
第3到n+2行：共n行，每行有两个整数，之间用1个空格隔开，分别表示这头奶牛所在的行和列。
Output
如果这块土地是安全的，输出0。
如果移走任意一头奶牛这块土地还是不安全，输出-1。
否则输出1，并且在下一行输出移走的那头奶牛的编号，如果有多个奶牛满足要求，输出输入序列中编号最小一个。
Examples
Input
5 5 5 1 1 2 4 3 1 2 2 2 1
Output
1 1
Solution C++
#include <cstdio> using namespace std; const int N(103); struct point { int r,c; }; point cow[N]; bool East[N]={false},North[N]={false},Removed[N]={false}; int r,c,n; bool safe() { for(int i=1;i<=n;i++) if(!Removed[i]) { East[i]=false; North[i]=false; for(int j=1;j<=n;j++) if(j!=i&&(!Removed[j])) { if(cow[j].c>cow[i].c&&cow[j].r==cow[i].r) East[i]=true; if(cow[j].r<cow[i].r&&cow[j].c==cow[i].c) North[i]=true; } if(East[i]&&North[i]) return false; } return true; } int main() { scanf("%d%d%d",&r,&c,&n); for(int i=1;i<=n;i++) scanf("%d%d",&cow[i].r,&cow[i].c); if(safe()) { printf("0\n"); return 0; } else for(int i=1;i<=n;i++) { Removed[i]=true; if(safe()) { printf("1\n%d\n",i); return 0; } else Removed[i]=false; } printf("-1\n"); return 0; }