2821: 打雷了
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:外部导入
提交:0
解决:
题目描述
某天,你被放在了一个可以划分成N*M个区域的矩形平原上。一开始你的位置在(1,1),出口在(N,M)。现在老天要开始打雷了。每秒钟将会有一道雷劈在(X,Y)的区域,你要是处于这个位置,后果……。更糟糕的是现在平原上有一些区域是导电的。如果雷电劈在一个导电的区域,电流将瞬间传播到所有与它连通的导电区域(一个区域和它上下左右四个区域连通。注意是导电区域,非导电区域就算连通也不会受影响),这些电流流经的区域你肯定都不能走了。现在时间紧迫,你每秒只能向上下左右4个方向移动一个区域,而且你要在最短的时间内走出平原(即用N+M-2秒)的时间。请你算出一共有多少种路线能够走到出口,方案可能比较多,你只需输出方案数MOD 100000001的值,如果你不能走到出口,则输出“Poor Y!”(不含引号);
输入
第一行2个整数 N,M
接下来N行每行M个数 描述这个平原 1表示该区域是导电区域,0表示不是。
接下来N+M-2行每行2个整数X,Y 表示1~N+M-2秒内每秒雷电劈下的坐标。
输出
输出一行 一个整数表示总方案MOD 100000001后的值 如果你不能走到出口则输出“Poor Y!”(不含引号)。
样例输入 复制
3 3
0 0 1
1 0 0
1 0 0
1 2
2 1
1 3
2 2
样例输出 复制
2
提示
40%的数据 3<=N,M<=100
100% 的数据 3<=N,M<=1000
1<=X<=N;
1<=Y<=M;