# Questions tagged [square-grid]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
894 views

### Can someone explain this formula for calculating Manhattan distance?

This is from a Kickstart problem: Note: The Manhattan distance between two squares (r1,c1) and (r2,c2) is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the absolute value. Then ...
64 views

### Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids

The question is: There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path exists, 1 means the cell is blocked and 2 means there exists gold in that cell. Task is to start from 0,...
20 views

### Grid treaversal with forbidden coordinates

What alorithm/heuristic can be applied to get a shortest path to all the blue coordinates below without going through red coordinates? starting and ending in bottom left(0,0). I have list of all the ...
111 views

### Finding the number of squares by connected coordinates

If I have a list of lists as below , ...
339 views

### Find smallest enclosing circle

On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known ...
79 views

### Finding the best poker hand in a connected grid structure where order matters

I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation. This grid has 12 random cards, in random positions. Each ...
120 views

### Maximizing number of selected squares in a grid

We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected ...
618 views

### Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...
395 views

### Algorithm to traverse all unblocked $1*1$ squares in a $n*m$ grid

Given a $n*m$ grid, some $1*1$ squares are blocked(can't be entered) and some are unblocked(can be entered). What is the algorithm which prints the shortest path, such that the path covers all ...
41 views

### Using counting to build a grid world

For this question, I have tried everything that I can think of, but cannot solve it. What I want to do is iterate over all possible values of $z_1$, but every method I use, it requires me to know ...
207 views

### Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces

Imagine a finite $n*n$ grid graph $G(V,E)$, much like a chessboard. Imagine further an undirected subgraph $H(V',E')$ of $G$. Let us call the squares of chessboard $G$ "faces". A DFS algorithm can ...
1k views

### Treewidth of k x k square grid graphs

According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most ...
6k views

### Draw a 5 × 5 grid graph. How many edges does the n × n grid graph have?

just confuse with this problem. What is n × n grid graph and how many edges it has?
1k views

### Square sub-grid with maximum sum

Given $N$ points in a grid having some weight, I have to find the side length of a square sub-grid with maximum sum of weight of points contained in that square sub-grid. Also square sub-grid must ...
176 views

### Upper bound on the number of hamiltonian cycles on a $n \times n$ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n$ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
217 views

### Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
2k views

### Are “Flow Free” puzzles NP-hard?

A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to ...
456 views

### Largest N squares that fit in a rectangle

I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally: Problem: Given N equal-sized squares and ...
788 views

### Shortest path from starting cell to all cells in the grid

I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells. How ...
This problem is about finding a route on a square grid. The starting point is $(1,1)$ and the target point $(n,m)$. I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$. ...