Skip to content

11532: 【原1532】金屋藏佳

题目

题目描述

author: greatwall1995, The 2014 ACM-ICPC Asia Bangkok Regional Contest 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1532

Description

在茫茫的千坝草原上生活着一只羊驼。羊驼的主人佳惊奇地发现每当羊驼听到自己的名字就会充满活力。这天,佳要回到遥远的故乡,为了保持羊驼的活力不让它苦闷致死,佳决定在一片\(m*n\)的草原上留下自己的记号。当然,“佳”这个字太复杂,所以佳决定用加号“+”来替代她的名字“佳”。

这些加号有如下性质:

  1. 由一条 1*L 和一条 L*1 的矩形叠加而成。
  2. 两个矩形的相交处位于他们各自的中点。
  3. L大小在[3,11]的区间内,且为奇数。
  4. 任何两个加号的中心不会重叠。
  5. 加号数量最多为9.

然而愚蠢的羊驼似乎并不能够理解佳的良苦用心。草原上密密麻麻的加号它根本无法辨别。现在已知草原每个格子上覆盖的加号数量,羊驼请你告诉它草原上有多少个加号,最后一个加号中心的位置在哪里(即在所有加号中心里,行号最大的那个。如果有多个中心行号同时最大,输出列号最大的中心坐标)。

数据保证解存在且唯一。

Input Format

第一行两个整数\(m,n\)表示网格的规模。

接下来\(m\)行,每行有\(n\)个由空格隔开的数字,表示草原每个格子上覆盖的加号数量。

Output Format

输出两行,第一行一个整数,表示加号的数量。第二行两个整数,分别表示最后一个加号中心的行号和列号(从1标号)。

Sample Input 1

5 5
0 1 1 0 0
1 1 2 0 0
1 2 1 1 1
0 0 1 0 0
0 0 1 0 0

Sample Output 1

2
3 3

Sample Input 2

10 11
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0
0 0 1 1 1 2 2 1 1 0 0
0 0 1 2 2 1 1 2 2 0 0
0 0 1 1 3 1 0 0 1 0 0
0 0 0 2 1 2 2 1 1 1 1
0 1 0 0 1 1 1 0 1 1 0
1 1 1 0 1 1 1 1 3 1 1
0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0

Sample Output 2

9
8 10

Limits

对于40%的数据,只有一个加号。

对于70%的数据,只有两个加号。

对于100%的数据,\(1≤m,n≤30\).

Hint

下图是样例二的图示(黄色部分表示每个加号的中心)


千坝草原位于甘肃,羊驼生活在美洲。所以千坝草原上是不可能有羊驼的,希望大家不要被误导。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!