AT_joi2009yo_d.薄氷渡り

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个寒冷的冬日，JOI 太郎君决定在广场上玩打破薄冰的游戏。广场是一个长方形，被划分为东西方向 $m$ 个、南北方向 $n$ 个区块，也就是说，总共有 $m \times n$ 个区块。此外，有些区块上有薄冰，有些区块上没有。JOI 太郎君按照以下规则，在打破薄冰的同时在区块间移动：

可以从任意有薄冰的区块开始打破薄冰。
可以向东西南北四个方向移动到相邻的、尚未被打破薄冰的区块。
移动到的新区块上的薄冰必须被打破。

请编写一个程序，求出 JOI 太郎君在打破薄冰的同时，最多能够移动经过的区块数。
其中 $1 \leq m \leq 90$ ， $1 \leq n \leq 90$ 。输入数据保证所有可能的移动方式不会超过 $20$ 万种。

输入格式

输入共 $n+2$ 行。
第 $1$ 行为整数 $m$ 。
第 $2$ 行为整数 $n$ 。
第 $3$ 行到第 $n+2$ 行的每一行包含 $m$ 个由空格分隔的 $0$ 或 $1$ ，表示每个区块是否有薄冰。
若将北边第 $i$ 行、西边第 $j$ 列的区块记为 $(i, j)$ （ $1 \leq i \leq n$ ， $1 \leq j \leq m$ ），则第 $i+2$ 行第 $j$ 个数为 $1$ 表示区块 $(i, j)$ 有薄冰，为 $0$ 表示没有薄冰。

输出格式

输出可以移动经过的区块数的最大值。

输入输出样例

输入#1
```
3
3
1 1 0
1 0 1
1 1 0
```
输出#1
```
5
```
输入#2
```
5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1
```
输出#2
```
5
```

说明/提示

样例解释 1

对于输入样例 $1$ ，给出最大值的移动方式示例：

样例解释 2

对于输入样例 $2$ ，给出最大值的移动方式示例：

对于输入样例 $2$ ，以下是不能得到最大值的移动方式示例：

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页