#P1713. [CZOJ 一周一测 R1 C] 恶灵群舞

[CZOJ 一周一测 R1 C] 恶灵群舞

恶灵成对,群舞惊雷。

题目背景

很久很久以前,王奕茹给邹锦舒出了一道毒瘤的数学题。见邹锦舒快速地回答出了她历尽千辛万苦才找到的难题,破口大骂。

第二天,王奕茹开始暴政邹锦舒。她将她的脚狠狠地踩在了邹锦舒的身上。邹锦舒一早上肚子都很痛,很痛。

于是乎,邹锦舒也准备着暴政王奕茹,尽管她有多么强。

有一天,邹锦舒和王奕茹竟然被好心的班主任分为了同桌。暴政的机会来了!呵呵。

但是,王奕茹在小学时是校柔道队的。如果要打赢她,只能靠智取。

在一个月黑风高的夜晚,邹锦舒偷偷潜入了教室找到了王奕茹。但邹锦舒没有发现的是,王奕茹预判了邹锦舒的预判,一脸核善地出现在邹锦舒身后。

妈呀,快跑!邹锦舒此时因受过度惊吓,学会了新技能——穿墙术!

题目描述

已知邹锦舒和王奕茹开始都在 (1,1)(1,1)。但是邹锦舒会穿墙术!

所谓穿墙术,就是说邹锦舒刚开始在 (x,y)(x,y),假设 (x,y+1)(x,y+1) 处有一堵墙,那么邹锦舒就可以穿墙到 (x,y+2)(x,y+2) 去。或者左,上,下的穿墙也可以。

但因为邹锦舒是蒟蒻,还没有学会如何穿其他位置的墙。但是王奕茹是不会穿墙的。

已知:邹锦舒不穿墙一步的代价是 aa,穿墙一步代价是 bb。七 12 班的教室是一个 (n,m)(n,m) 的矩阵。教室中有一部分是有墙的,用 11 表示。没墙的用 00 表示。

邹锦舒想问你能不能摆脱王奕茹的追捕。能的话请在第二行输出邹锦舒摆脱王奕茹追捕的最小代价和所到达的地方。

输入格式

第一行四个整数 n,m,a,bn,m,a,b,表示七 12 班的行数和列数以及邹锦舒不穿墙和穿墙的代价。

2n+12 \sim n+1 行,每行 mm 个整数,代表七 12 班的地形。有墙是 11,没墙是 00

输出格式

输出共一行或两行。

第一行输出 YesNo,即邹锦舒能不能摆脱王奕茹的追捕。

若第一行是 Yes,第二行请输出最小的代价和所到的地方。

只因不想劳累陈煜轩,若有最小的代价相同的且都可以摆脱王奕茹的追捕,请输出 xx 最大的。若 xx 都一样,请输出 yy 最大的。

数据保证 (1,1)(1,1) 不是墙。

所到的地方用坐标表示,详见样例#2。

注意:(x,y)(x,y) 代表 xxyy 列。左上角为 (1,1)(1,1)

3 3 114 514
0 0 1
0 0 0
0 0 0
No
3 3 1 514
0 1 0
1 0 1
0 1 0
Yes
514 (3,1)

样例解释

对于样例#1,明显的,邹锦舒找不到他的藏身之处,终究会被王奕茹逮捕。

对于样例#2,邹锦舒的路线是 (1,1)(3,1)(1,1)\to(3,1),用了一次穿墙。

数据范围

测试点编号 n,mn,m a,ba,b 特殊性质
11 100\leq 100 109\leq 10^9 A\tt A
242\sim 4 2\leq 2 10\leq 10
585\sim 8 20\leq 20 105\leq 10^5
9209\sim 20 100\leq 100 109\leq 10^9

特殊性质 A\tt{A}:保证教室没有墙。