Temukan koordinat semua persegi panjang dengan angka 1 yang berdekatan dalam larik 2D dalam Javascript

Saya telah menemukan banyak pertanyaan yang menanyakan tentang cara mencari persegi panjang terbesar yang bersebelahan dalam larik 2D, dan ada pula yang menanyakan jumlah persegi panjang, tetapi hanya satu yang berhubungan dengan mencari koordinat, lebar, dan tinggi semua persegi panjang yang diperlukan. mencakup area seluas 1s dalam 2D ​​1s dan 0s.

Pertanyaannya (Menemukan persegi panjang dalam kisi blok 2d) memiliki solusinya tetapi sulit untuk diikuti karena merujuk pada blok kode eksternal.

Saya berurusan dengan array 2D yang membentuk piksel huruf:

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

Output yang diinginkan di sini adalah seperti:

[[4,0,6,17],[7,0,16,2],[7,7,15,9],[7,15,15,17]]

Di mana setiap larik berisi koordinat kiri atas dan koordinat kanan bawah (metode apa pun yang mendapatkan kiri atas serta lebar dan tinggi juga berfungsi).

Bisakah seseorang memberikan psudocode (atau Javascript) untuk pertanyaan yang diajukan sebelumnya atau algoritma lain yang berfungsi, atau memberikan penjelasan lebih mendalam tentang langkah-langkah yang diperlukan?


javascript arrays multidimensional-array
person Freddie R    schedule 19.02.2019    source sumber

Jawaban (1)


arrow_upward
1
arrow_downward

Berikut cara melakukannya dengan menggunakan algoritma sederhana.

  1. Hitung luas seluruh persegi panjang -> A
  2. While the area of the rectangles found so far is smaller than A
    1. Find a new rectangle
      1. Find the upper left corner, scan the matrix and stop at the first 1 found
      2. Temukan pojok kanan bawah, mulai dari pojok kiri atas, pindai matriks dan berhenti di 0 pertama yang ditemukan
    2. Tandai persegi panjang yang ditemukan dengan mengatur setiap sel ke selain 1
    3. Tambahkan luasnya ke luas akumulasi
    4. Dorong persegi panjang ke daftar

const mat = [
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//0
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//1
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//2
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//3
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//4
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//5
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//6
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0],//7
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0],//8
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0],//9
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//10
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//11
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//12
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//13
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//14
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//15
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//16
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0] //17
];

const W = mat[0].length;
const H = mat.length;

// get the area covered by rectangles
let totalRectArea = 0;
for (let i = 0; i < W; ++i) {
  for (let j = 0; j < H; ++j) {
    totalRectArea += mat[j][i] > 0 ? 1 : 0;
  }
}

const rects = [];
let rectArea = 0;

// find all rectangle until their area matches the total
while (rectArea < totalRectArea) {
  const rect = findNextRect();
  rects.push(rect);
  markRect(rect);
  rectArea += (rect.x2 - rect.x1 + 1) * (rect.y2 - rect.y1 + 1);
}

console.log(rects);

function findNextRect() {
  // find top left corner
  let foundCorner = false;
  const rect = { x1: 0, x2: W-1, y1: 0, y2: H-1 };
  for (let i = 0; i < W; ++i) {
    for (let j = 0; j < H; ++j) {
      if (mat[j][i] === 1) {
        rect.x1 = i;
        rect.y1 = j;
        foundCorner = true;
        break;
      }
    }
    if (foundCorner) break;
  }
  // find bottom right corner
  for (let i = rect.x1; i <= rect.x2; ++i) {
    if (mat[rect.y1][i] !== 1) {
      rect.x2 = i-1;
      return rect;
    }
    for (let j = rect.y1; j <= rect.y2; ++j) {
      if (mat[j][i] !== 1) {
        rect.y2 = j-1;
        break;
      }
    }
  }
  return rect;
}

// mark rectangle so won't be counted again
function markRect({ x1, y1, x2, y2 }) {
  for (let i = x1; i <= x2; ++i) {
    for (let j = y1; j <= y2; ++j) {
      mat[j][i] = 2;
    }
  }
}

person jo_va    schedule 19.02.2019
comment
Ini sangat membantu. Ini berfungsi (memberikan peningkatan kecepatan ~10x), dan jauh lebih mudah dipahami daripada apa pun yang pernah saya temui, terima kasih. - person Freddie R; 19.02.2019
comment
Saya menggunakan kode ini di perpustakaan javascript sumber terbuka, bagaimana Anda ingin diakui? - person Freddie R; 24.02.2019