Questions tagged [square-grid]
The square-grid tag has no usage guidance.
21
questions
6
votes
1answer
802 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 ...
0
votes
1answer
55 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,...
1
vote
0answers
19 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 ...
2
votes
2answers
105 views
3
votes
1answer
264 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 ...
2
votes
1answer
71 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 ...
4
votes
1answer
113 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 ...
2
votes
2answers
561 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 :
...
2
votes
0answers
381 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 ...
0
votes
0answers
40 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 ...
4
votes
1answer
199 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 ...
7
votes
1answer
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 ...
-2
votes
3answers
5k 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?
1
vote
1answer
714 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 ...
5
votes
0answers
169 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 ...
3
votes
0answers
208 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 ...
15
votes
1answer
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 ...
4
votes
2answers
454 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 ...
1
vote
1answer
771 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 ...
0
votes
1answer
183 views
Find a continuous path filling whole 3xN grid going through certain points in given order
I've got a grid consisting of squares that is 3 squares high and N squares long.
Some of the squares are filled with numbers that are not greater than 3*N. You can move only to squares that are below,...
5
votes
1answer
620 views
Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves
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)$.
...
