Ich habe eine Weile darüber nachgedacht. Ich habe folgende Methode gefunden:
1) Beseitigen Sie alle Nullen am Rand - ändern Sie ihren Wert auf 2
2) Fluten Sie die Matrix um die 2er herum
Dies hinterlässt nur eine Insel von Nullen, die nun auf Konvexität getestet werden kann. Also für jede Insel:
3) Suchen Sie nach dem Bereich des 0-Werts in X und Y - geben Sie ein potenzielles inneres Rechteck
4) Wenn das innere Rechteck eine 1 enthält ODER das äußere Rechteck eine 0 enthält, fluten Sie diese Insel mit 2en, da sie nicht konvex (und daher kein Rechteck) ist
Unter der Annahme, dass Sie einen guten "Flood Fill"-Algorithmus finden können (nicht wie meinen), sollte dies effizient sein, um den Suchraum schnell zu reduzieren.
Und jetzt für den Code (sorry, es ist C#):
using System;
using System.Collections.Generic;
namespace Test
{
class MainClass
{
static private int [,] matrix = new int[,] {
{0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
{0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
{0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
{0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
{0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,1,0,0,1,1,1,0,1,1,0},
{0,0,1,1,1,1,0,0,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1,1,0,0,0,0}
};
static private int width = matrix.GetLength(0);
static private int height = matrix.GetLength(1);
private const int DEAD = 2;
private const int RECT = 3;
public static void Main (string[] args)
{
//width = matrix.GetLength(0);
//height = matrix.GetLength(1);
PrintMatrix ();
EliminateFromEdges (DEAD);
PrintMatrix ();
FloodFill (DEAD); // sehr ineffizient - finden Sie einen besseren "Flood-Fill"-Algorithmus
PrintMatrix ();
// Testen Sie jede Insel mit Nullen auf Konvexität
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (matrix[i,j] == 0)
{
if (TestIsland(i,j) == false)
{
// Diese Insel ausschließen, da sie nicht konvex ist
matrix[i,j] = DEAD;
FloodFill(DEAD);
PrintMatrix ();
}
else
{
// Dieses Rechteck als solches kennzeichnen
matrix[i,j] = RECT;
FloodFill(RECT);
PrintMatrix ();
}
}
}
}
// Wir sind fertig, alles, was als RECT gekennzeichnet ist, kann erweitert werden, um die Rechtecke zu erhalten
PrintMatrix ();
}
// Markieren Sie alle Nullen am Rand der Matrix als 'tot'
static private void EliminateFromEdges(int value)
{
for (int i = 0; i < width; i++)
{
if (matrix [i, 0] == 0)
{
matrix [i, 0] = value;
}
if (matrix [i, height - 1] == 0)
{
matrix [i, height - 1] = value;
}
}
for (int j = 1; j < height - 1; j++)
{
if (matrix [0, j] == 0)
{
matrix [0, j] = value;
}
if (matrix [width - 1, j] == 0)
{
matrix [width - 1, j] = value;
}
}
}
// Verbreiten Sie einen Wert auf benachbarte Zellen
static private void FloodFill (int value)
{
bool change_made = true; // auf true setzen, um anzufangen
while (change_made) {
change_made = false;
for (int i = 1; i < width - 1; i++) {
for (int j = 1; j < height - 1; j++) {
if ((matrix [i, j] == 0) &&
((matrix [i - 1, j] == value) ||
(matrix [i + 1, j] == value) ||
(matrix [i, j - 1] == value) ||
(matrix [i, j + 1] == value))) {
matrix [i, j] = value;
change_made = true;
}
}
}
}
}
static private bool TestIsland (int x, int y)
{
// Finde den konvexen Bereich der Insel
int x2 = x;
int y2 = y;
while (matrix[++x2, y] == 0);
x2--;
while (matrix[x,++y2] == 0);
y2--;
// Überprüfe die inneren Zellen (möchte alles Nullen haben)
for (int i = x; i <= x2; i++)
{
for (int j = y; j <= y2; j++)
{
if (matrix[i,y] != 0)
{
return false;
}
}
}
// Überprüfe die umliegenden Zellen (möchte alles Einsen haben)
x--; y--;
x2++; y2++;
for (int i = x; i <= x2; i++)
{
if ((matrix[i,y] != 1) || (matrix[i,y2] != 1))
{
return false;
}
}
for (int j = y + 1; j <= y2 - 1; j++)
{
if ((matrix[x,j] != 1) || (matrix[x2,j] != 1))
{
return false;
}
}
return true;
}
// Zum Debuggen
static private void PrintMatrix ()
{
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
switch(matrix[i,j])
{
case DEAD:
Console.Write("-");
break;
case RECT:
Console.Write("+");
break;
default:
Console.Write(matrix[i,j]);
break;
}
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
Die Ausgabe dieses Codes
000000001111000
011111101001010
010000101001010
010000101001010
010000101000010
010000101000010
011111101001010
000000001111000
001111000000000
001001001110110
001111001010000
000000001110000
--------1111---
-1111110100101-
-1000010100101-
-1000010100101-
-1000010100001-
-1000010100001-
-1111110100101-
-0000000111100-
-0111100000000-
-0100100111011-
-0111100101000-
--------111----
--------1111---
-111111-1--1-1-
-100001-1--1-1-
-100001-1--1-1-
-100001-1----1-
-100001-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----
