How can I optimize double for loop in matrix

Question

I am trying to optimize a function called place_block. It is meant to give the best row, col coordinate in the matrix to place a given block of row and column size.

My current implementation is unreadable and bad practice. I'm looking for a better way to put it.

// Generates the best possible solution to place a given block of size
vector<int> place_block(char grid[8][8], int block_size_r, int block_size_col) {
 vector<int> rowcol;
// Based on a block size of block_size_r x block_size_col generate a convient position to place it in the grid without
// Overflow
int row = 0;
int col = 0;
int row_max = 8 - block_size_r;
int col_max = 8 - block_size_col;
// Randomly Iterate through the grid till a perfect row by col is achieved where the block can be placed in the grid
// without overflowing
 // Check if the block can be placed in the grid without overflowing and if the block is not overlapping another block in the grid
 // Ensure that each block is accounted for. Ex. for a 2x2 block, ensure that all 4 spaces are empty, based off block_size_r and block_size_col
for (int i = 0; i < 8; i++) {
 for (int j = 0; j < 8; j++) {
 if (isEmpty(grid, i, j)) {
 if (block_size_r == 1 && block_size_col == 1) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 } else if (block_size_r == 1 && block_size_col == 2) {
 if (isEmpty(grid, i, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 1 && block_size_col == 3) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 1 && block_size_col == 4) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 1 && block_size_col == 5) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i, j + 4)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 2 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 2 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 2 && block_size_col == 3) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
 isEmpty(grid, i, j + 2) && isEmpty(grid, i + 1, j + 2)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 2 && block_size_col == 4) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
 isEmpty(grid, i, j + 2) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i + 1, j + 3)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 3 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 3 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i, j + 1) &&
 isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 3 && block_size_col == 3) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i, j + 1) &&
 isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i, j) &&
 isEmpty(grid, i, j + 2) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 2, j + 2)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 4 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 4 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) &&
 isEmpty(grid, i + 3, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 5 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 5 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
 isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 4, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 6 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 6 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i, j + 1) &&
 isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 3, j + 1) &&
 isEmpty(grid, i + 4, j + 1) && isEmpty(grid, i + 5, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 7 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 7 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j) &&
 isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 2, j + 1) &&
 isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 4, j + 1) && isEmpty(grid, i + 5, j + 1) &&
 isEmpty(grid, i + 6, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 8 && block_size_col == 1) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j) &&
 isEmpty(grid, i + 7, j)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 8 && block_size_col == 2) {
 if (isEmpty(grid, i + 1, j) && isEmpty(grid, i + 2, j) && isEmpty(grid, i + 3, j) &&
 isEmpty(grid, i + 4, j) && isEmpty(grid, i + 5, j) && isEmpty(grid, i + 6, j) &&
 isEmpty(grid, i + 7, j) && isEmpty(grid, i, j + 1) && isEmpty(grid, i + 1, j + 1) &&
 isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 4, j + 1) &&
 isEmpty(grid, i + 5, j + 1) && isEmpty(grid, i + 6, j + 1) && isEmpty(grid, i + 7, j + 1)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } // check 2x5
 else if (block_size_r == 2 && block_size_col == 5) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i, j + 4) && isEmpty(grid, i + 1, j) && isEmpty(grid, i + 1, j + 1) &&
 isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) && isEmpty(grid, i + 1, j + 4)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 3 && block_size_col == 5) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i, j + 4) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) &&
 isEmpty(grid, i + 1, j + 3) && isEmpty(grid, i + 1, j + 4) && isEmpty(grid, i + 2, j + 1) &&
 isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) && isEmpty(grid, i + 2, j + 4)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 4 && block_size_col == 5) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i, j + 4) && isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) &&
 isEmpty(grid, i + 1, j + 3) && isEmpty(grid, i + 1, j + 4) && isEmpty(grid, i + 2, j + 1) &&
 isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) && isEmpty(grid, i + 2, j + 4) &&
 isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 3, j + 2) && isEmpty(grid, i + 3, j + 3) &&
 isEmpty(grid, i + 3, j + 4)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } // 3x4
 else if (block_size_r == 3 && block_size_col == 4) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) &&
 isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 4 && block_size_col == 4) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) &&
 isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) &&
 isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 3, j + 2) && isEmpty(grid, i + 3, j + 3)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 } else if (block_size_r == 5 && block_size_col == 4) {
 if (isEmpty(grid, i, j + 1) && isEmpty(grid, i, j + 2) && isEmpty(grid, i, j + 3) &&
 isEmpty(grid, i + 1, j + 1) && isEmpty(grid, i + 1, j + 2) && isEmpty(grid, i + 1, j + 3) &&
 isEmpty(grid, i + 2, j + 1) && isEmpty(grid, i + 2, j + 2) && isEmpty(grid, i + 2, j + 3) &&
 isEmpty(grid, i + 3, j + 1) && isEmpty(grid, i + 3, j + 2) && isEmpty(grid, i + 3, j + 3) &&
 isEmpty(grid, i + 4, j + 1) && isEmpty(grid, i + 4, j + 2) && isEmpty(grid, i + 4, j + 3)) {
 rowcol.push_back(i);
 rowcol.push_back(j);
 return rowcol;
 }
 }
 }
 }
}
 rowcol.push_back(row);
 rowcol.push_back(col);
 std::cout << "row: " << row << " col: " << col << std::endl;
 return rowcol;
}

I'm looking for the best way to optimize what I've implemented. Thanks in the future!

• Toby Speight: Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles.
• Toby Speight: I think you'll need to show us your isEmtpy() function. And is vector an alias for std::vector?
• greybeard: (There is no isEmtpy.)

Answer 1

You can drastically improve your code, if you also use loops for testing whether block positions are free.

So, first iterate through the outer grid (Of course only until grid size - height and same for columns). Then for each position row and col where you currently are, check from this position, if the block would fit. Again with a loop.

I extended the example and allow for an rectangular grid of any size. But of course, at the beginning of the function, I added a sanity check that everything fits together.

Please see below one potential improvement proposal:

#include <iostream>
#include <vector>
#include <algorithm>
struct Coordinate {
 size_t row{};
 size_t col{};
};
std::vector<Coordinate> findPositions(std::vector<std::vector<int>>& grid, size_t width, size_t height) {
 // Resulting potential positions
 std::vector<Coordinate> result{};
 // sanity check. Check min and max extension of grid and block
 if (
 // Prevent the grid has no rows
 not grid.empty() and
 // Check, the all columns have the same width
 std::all_of(grid.begin(), grid.end(), [&](const std::vector<int>& row) { return row.size() == grid.front().size(); })
 // Block to fit has at least one row and column and is not bigger than the grid
 and (width > 1) and (height > 1) and (width < grid.front().size()) and (height < grid.size())) {
 }
 // Check for all row and columns of the grid
 // But only to a position, where the block could fit
 for (size_t row = 0; row <= (grid.size() - height); ++row) 
 for (size_t col = 0; col <= (grid.front().size() - width); ++col) {
 bool potentialFit = true;
 // Now check, if all cells of the block starting at this row / col positions are empty
 for (size_t blockRow = row; potentialFit and (blockRow < (row + height)); ++blockRow)
 for (size_t blockCol = col; potentialFit and (blockCol < (col + width)); ++blockCol)
 // If this cell is occupied
 if (grid[blockRow][blockCol] != 0)
 // Indicate that we have no soulition and stop loops
 potentialFit = false;
 // We found a fit. store the postion
 if (potentialFit)
 result.push_back({ row, col });
 }
 return result;
}
int main() {
 std::vector<std::vector<int>> grid{
 { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 { 0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
 { 0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0},
 { 1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
 { 0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0},
 { 0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0},
 };
 // Look where a 3x4 block will fit in above grid
 for (const Coordinate& c : findPositions(grid, 3, 4))
 std::cout << "Row: " << c.row << "\tCol: " << c.col << '\n';
}

if you want to accept square grids only, you may change in the sanity check:

std::all_of(grid.begin(), grid.end(), [&](const std::vector<int>& row) { return row.size() == grid.size(); })

Of course you can also allow blocks with same width and height only; simply add a new condition.