You are given a grid with both sides equal to N/N. Rows and columns are numbered from 0/0 to N−1/N−1. There is a castle on the intersection of the aath row and the bbth column.
Your task is to calculate the minimum number of steps it would take to move the castle from its initial position to the goal position [c/d].
It is guaranteed that it is possible to reach the goal position from the initial position.
Link
Castle on the Grid
Complexity:
time complexity is O[N^2] or O[N^3]
space complexity is O[N^2]
Execution:
This solution works with the task as a 2D array. There are options available where you treat the task as a graph problem. In both cases each node it visited exactly once using BFS. On each node, I generate all nodes that are connected to this node in a straight line that is not broken by a ‘X’. I keep the distance data [integer] in the array itself. I store the nodes that have to be visited in a FIFO queue. Once the top element in the queue is the end, I terminate the algorithm. The data stored in the array are these:
- X – blocked
- . – not visited yet
- [int] – already visited. Value is the number of steps from the beginning.
Solution:
from collections import deque
class Point:
def __init__[self, x, y]:
self.x = x
self.y = y
def __str__[self]:
return "X=%d,Y=%d" % [self.x, self.y]
def getPointsFromPoint[N, arr, point]:
x = point.x
y = point.y
points = []
while x > 0:
x -= 1
if arr[x][y] == 'X':
break
points.append[Point[x,y]]
x = point.x
while x < N-1:
x += 1
if arr[x][y] == 'X':
break
points.append[Point[x,y]]
x = point.x
while y > 0:
y -= 1
if arr[x][y] == 'X':
break
points.append[Point[x,y]]
y = point.y
while y < N-1:
y += 1
if arr[x][y] == 'X':
break
points.append[Point[x,y]]
return points
def solveCastleGrid[N, arr, start, end]:
q = deque[[start]]
arr[start.x][start.y] = 0
while q:
current_point = q.pop[]
current_distance = arr[current_point.x][current_point.y]
points = getPointsFromPoint[N, arr, current_point]
for p in points:
if arr[p.x][p.y] == '.':
arr[p.x][p.y] = current_distance + 1
q.appendleft[p]
if p.x == end.x and p.y == end.y:
return current_distance + 1
return -1
if __name__ == '__main__':
N = input[]
arr = [0] * N
for i in xrange[N]:
arr[i] = list[raw_input[]]
start_x, start_y, end_x, end_y = map[int, raw_input[].split[]]
print solveCastleGrid[N, arr, Point[start_x, start_y], Point[end_x, end_y]]
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.
In this HackerRank Castle on the Grid Interview preparation kit problem you have Given a grid, a start, and a goal, determine the minimum number of moves to get to the goal.
Problem solution in Python programming.
import numbers
import math
from collections import namedtuple,deque
class point[namedtuple["point", "i j"]]:
def __eq__[self,o]:
return self.i == o.i and self.j == o.j
def __ne__[self, o]:
return self.i != o.i or self.j != o.j
def __lt__[self, o]:
return self.i < o.i or self.j < o.j
def __gt__[self, o]:
return self.i > o.i or self.j > o.j
def __le__[self, o]:
return self.i = o.j
def __rshift__[self,o]:
return self.i >= o.i and self.j >= o.j
def __lshift__[self,o]:
return self.i = n]
return -1;
if[vlist[tx][ty] == 'X']
return -1;
if[visited[tx][ty] == 1]
return 0;
visited[tx][ty] = 1;
pst.push_back[tx + ty *n];
if[tx == x1 && ty == y1]
return 1;
return 0;
}
int main[] {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n;
cin >> n;
vector vlist;
vector vvst;
vlist.resize[n];
vvst.resize[n];
for[int i = 0; i < n; i ++]
{
for[int j =0; j < n; j ++]
{
char c;
cin >> c;
vlist[i].push_back[c];
vvst[i].push_back[0];
}
}
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
deque pst;
pst.push_back[x0 + n * y0];
int level = 0;
bool found = false;
deque tempst;
while[true]
{
if[pst.empty[]]
{
pst = tempst;
tempst.clear[];
}
if[pst.empty[] || found]
break;
level ++;
while[!pst.empty[]]
{
if[found]
break;
int v = pst.front[];
pst.pop_front[];
int tx = v % n;
int ty = v / n;
for[int k = tx - 1; k >=0; k --]
{
int rn = func[vlist, tempst, vvst, k, ty, x1, y1];
if[rn == -1]
break;
else if[rn == 1]
{
found = true;
break;
}
}
for[int k = tx + 1; k < n; k ++]
{
int rn = func[vlist, tempst, vvst, k, ty, x1, y1];
if[rn == -1]
break;
else if[rn == 1]
{
found = true;
break;
}
}
for[int k = ty - 1; k >=0; k --]
{
int rn = func[vlist, tempst, vvst, tx, k, x1, y1];
if[rn == -1]
break;
else if[rn == 1]
{
found = true;
break;
}
}
for[int k = ty + 1; k < n; k ++]
{
int rn = func[vlist, tempst, vvst, tx, k, x1, y1];
if[rn == -1]
break;
else if[rn == 1]
{
found = true;
break;
}
}
}
}
cout grid.length - 1 || cc > grid[0].length - 1] break;
// stop visited or blocked cells
if [visited[rr][cc].visited] continue;
if [grid[rr][cc] === 'X'] break;
colQueue.push[cc];
rowQueue.push[rr];
visited[rr][cc].visited = true;
visited[rr][cc].parent = [row, col];
}
}
}
}
function main[] {
const ws = fs.createWriteStream[process.env.OUTPUT_PATH];
const n = parseInt[readLine[], 10];
let grid = [];
for [let i = 0; i < n; i++] {
const gridItem = readLine[];
grid.push[gridItem];
}
const startXStartY = readLine[].split[' '];
const startX = parseInt[startXStartY[0], 10];
const startY = parseInt[startXStartY[1], 10];
const goalX = parseInt[startXStartY[2], 10];
const goalY = parseInt[startXStartY[3], 10];
const result = minimumMoves[grid, startX, startY, goalX, goalY];
ws.write[result + '\n'];
ws.end[];
}
Video liên quan