1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

题面描述:

在这个问题中,给定一个二维数组表示黑白棋盘,黑棋用1表示,白棋用0表示。目标是找到一个最大的正方形,其边界由黑棋(1)组成,并返回该正方形的右下角坐标及其宽度。如果有多个满足条件的正方形,则返回右下角行号最小的,若行号相同则返回列号最小的。输入包括棋盘的行数和列数,以及棋盘的具体内容,输出为一个列表,包含满足条件的最大正方形的信息。

思路:动态规划/前缀和

原题来自于LeetCode 1139. 最大的以 1 为边界的正方形

我们只需要在此基础上找到这个正方形的右下角即可。

P2347.第3题-平面灯阵中寻找最大正方形边界

    1000ms Tried: 412 Accepted: 72 Difficulty: 6 所属公司 : 华为
    算法与标签>动态规划

本题考察的LeetCode原题

LeetCode 1139. 最大的以 1 为边界的正方形

题目描述

现在有一个二维数组来模拟一个黑白棋盘,将黑白棋子置于方格之中,棋盘中每个位置都放入黑棋或白棋,分别对应数组每个元素取值只能为 111 或 000 (黑棋为 111 , 白棋为 000),现在需要找一个正方形边界,其每条边上的棋子都是黑棋(对应数组中元素的值为 111 )的,且该正方形面积最大。

输入描述

输入第一行为棋盘的行数(二维数组的行数)

输入第二行为棋盘的列数(二维数组的列数)

紧接着为模拟棋盘的二维数组 arrarrarr

1<arr.length≤2001 < arr.length \le 2001<arr.length≤200

1<arr[0].length≤2001 < arr[0].length \le 2001<arr[0].length≤200

输出描述

返回满足条件的面积最大正方形边界信息。返回信息[r,c,wr,c,wr,c,w],其中 rrr , ccc 分别代表方阵右下角的行号和列号,www 代表正方形的宽度。如果存在多个满足条件的正方形,则返回 rrr 最小的,若 rrr 相同,返回 ccc 最小的正方形。

样例1

输入

4
5
1 0 0 0 1
1 1 1 1 1
1 0 1 1 0
1 1 1 1 1

输出

[3,2,3]

说明:满足条件且面积最大的正方形边界,其右下角的顶点为 [3,2],即行号为 333 ,列好为 222 ,其宽度为 333 ,因此返回信息为 [3,2,33,2,33,2,3]。

样例2

输入

3
3
1 0 0
0 1 0
0 0 1

输出

[0,0,1]

**说明:**满足条件且面积最大的正方形边界有三个。即为 [0,0,10,0,10,0,1]、[1,1,11,1,11,1,1]、[2,2,12,2,12,2,1],根据要求,如果满足条件有多个,则返回 rrr 最小,即为[0,0,10,0,10,0,1]

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 0, 81ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?