KnightL on a Chessboard
KnightL on a Chessboard
+ 0 comments int travel (int n, int a, int b) { vector<vector<bool>> visited(n, vector<bool>(n, false)); queue<vector<pair<int, int>>> Q; Q.push({{0, 0}}); while (!Q.empty()) { vector<pair<int, int>> T = Q.front(); Q.pop(); int x = T.back().first; int y = T.back().second; vector<int> one = {-1, 1}; set<pair<int, int>> neighbours;; for (int i : one) { for (int j : one) { neighbours.insert({x+i*a, y+j*b}); neighbours.insert({x+i*b, y+j*a}); } } for (auto p : neighbours){ int x2 = p.first, y2 = p.second; if (x2 == n-1 and y2 == n-1) return T.size(); if (0 <= x2 and x2 < n and 0 <= y2 and y2 < n and !visited[x2][y2]) { vector<pair<int, int>> history = T; history.push_back({x2, y2}); Q.push(history); visited[x2][y2] = true; } } } return -1; } vector<vector<int>> knightlOnAChessboard(int n) { vector<vector<int>> answer(n-1, vector<int>(n-1)); for (int i=1; i < n; i++) { for (int j=1; j < n; j++) { answer[i-1][j-1] = travel(n, i, j); } } return answer; }
+ 0 comments For every position,the Knight has at most 8 directions to go.Therfore, all the positions form a graph that each vertex has at most 8 edges. If we want the Knight move from
(0,0)
to(n-1,n-1)
within the minimum steps, we can use BFS(Breadth-First Search) to enumerate all possibilities. Before we use BFS, we can simplify the situations: Especially, whena==b
, we can be certain that the minimum steps that the Knight will take is to move along the diagonal. Thus, the next thing to do is to judge whether(n-1)%a==0
is valid or not. And the result of(n-1)/a
is the answer fora==b
. Here is my C++ solution.C++ solution of Knight on a Chessboard. Thanks for @sumesh1999. I revised and optimized my code after referring to your code.
int BFS(int i,int j,int n){ queue<pair<pair<int,int>,int>> q; int id[n][n]; memset(id,0,sizeof(id)); id[0][0]=1; vector<pair<int,int>> move={{i,j},{i,-j},{-i,j},{-i,-j},{j,i},{j,-i},{-j,i},{-j,-i}}; q.push({{0,0},0}); while(!q.empty()){ int x=q.front().first.first,y=q.front().first.second,count=q.front().second; for(int i=0;i<8;i++){ int tempx=x+move[i].first,tempy=y+move[i].second; if(tempx>=0 && tempy>=0 && tempx<n && tempy<n && id[tempx][tempy]==0){ q.push({{tempx,tempy},count+1}); id[tempx][tempy]=1; } } if(x==n-1 && y==n-1) return count; q.pop(); } return -1; } vector<vector<int>> knightlOnAChessboard(int n) { int d=n-1; vector<vector<int>> ans(d,vector<int>(d,0)); for(int i=0;i<d;i++){ for(int j=0;j<d;j++){ if(i==j){ if(d%(i+1)==0) ans[i][j]=d/(i+1); else ans[i][j]=-1; } else{ if(ans[i][j]==0){ ans[i][j]=BFS(i+1,j+1,n); } ans[j][i]=ans[i][j]; } } } return ans; }
+ 0 comments Here is my solution in java, javascript, python, C, C++, Csharp HackerRank KnightL on a Chessboard Solution
+ 0 comments Here is the solution of KnightL on a Chessboard Click Here
+ 0 comments For something different, here's a 'supercomputer' solution in Java 17. This performs N-way search over all the knights at once, given N threads. Note it may run slower on single-thread hardware.
class Result { /* * Compute minimal distance for a knight making L-shaped moves. * * Notes: Essentially a mere implementation problem, but we can * parallelize the search, and store identical states (homologs). * * Uses a reductive design for potential concurrency gains, * backed by a Red-Black Tree of dependencies (ConcurrentHashMap). * (remove .parallel for sequential hardware) * * 𝚯(N) runtime for each Knight, given N = board size (n * n). * * Total runtime 𝚯(N log N) with unlimited processors and neighbor * reducing on, otherwise 𝚯(knights * searches) = 𝚯(n * N) = 𝚯(n³). * * 𝚯(N) space complexity for each search */ static Map<Set<Integer>, Integer> memo = new ConcurrentHashMap<>(); public static List<List<Integer>> knightOnAChessboard(int n) { return IntStream.range(1, n) .parallel() .mapToObj(x -> IntStream.range(1, n) .parallel() .map(y -> memoize(new Knight(x, y, n))) .boxed().toList()).toList(); } /* Store mirrors of this Knight for simple dynamic programming. */ private static Integer memoize(Knight k) { return memo.merge(k.homolog(), distanceOf(k), (a, b) -> a); } /* Compute the board distance for this Knight, via BFS */ private static Integer distanceOf(Knight k) { final Point destination = new Point(k.n - 1, k.n - 1); final Point origin = new Point(new Point(0, 0)); Deque<Point> queue = new ArrayDeque<>(List.of(origin)); Set<Point> alreadyVisited = new HashSet<>(List.of(origin)); k.atlas.put(origin, 0); do { Point current = queue.remove(); if (current.equals(destination)) { return k.atlas.get(current); } else { alreadyVisited.add(current); queue.addAll(k.neighborsOf(current)); queue.removeAll(alreadyVisited); } } while (!queue.isEmpty()); return -1; } } /* * Knight moving in (dx, dy) fashion on chessboard. * The knight keeps an 'odometer' of the minimum moves * to reach a given square. */ class Knight { Map<Point, Integer> atlas = new ConcurrentHashMap<>(); final int x; final int y; final int n; Knight(int x, int y, int n) { this.x = x; this.y = y; this.n = n; } /* Enumerate all positions reachable by this Knight */ public List<Point> neighborsOf(Point p) { return Direction.all() .flatMap(d -> travel(p, d)) .filter(this::isValid) .toList(); } private Stream<Point> travel(Point p, Direction d) { return Stream.of(pointOf(p, d, x, y), pointOf(p, d, y, x)); } private Point pointOf(Point p, Direction sign, int dx, int dy) { Point q = p.getLocation(); q.translate(dx * sign.dx, dy * sign.dy); atlas.merge(q, atlas.get(p) + 1, Math::min); return q; } /* Represent the cardinal directions */ private enum Direction { U(1,1), D(-1,-1), L(-1, 1), R(1, -1); final int dx; final int dy; private Direction(int dx, int dy) { this.dx = dx; this.dy = dy; } static Stream<Direction> all() { return Arrays.stream(Direction.values()); } } private boolean isValid(Point p) { return p.y < n && p.x < n && p.y >= 0 && p.x >= 0; } Set<Integer> homolog() { if(x == y) return Set.of(x); return Set.of(x, y); } }
Sort 118 Discussions, By:
Please Login in order to post a comment