` ``` #include #include #include using namespace std; class Solution { int numRows; int numCols; public : Solution():numRows(10),numCols(9) { } bool isreachable(const vector& start, const vector& target, const vector>& blocked) { vector> board(numRows, vector(numCols,1)); // 0 = blocked square for(auto& block : blocked) { board[block[0]][block[1]] = 0; } // leg square directions vector> legSquareDirs({{1,0},{-1,0},{1,0},{-1,0},{0,1},{0,-1},{0,1},{0,-1}}); // move directions vector> dirs({{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}}); queue> q; q.push(start); board[start[0]][start[1]] = -1; // mark-on-ENQUEUE: start is now visited while(!q.empty()){ vector curSquare = std::move(q.front()); q.pop(); // check for target if(curSquare[0] == target[0] && curSquare[1] == target[1]) return true; for(size_t i = 0; i < dirs.size(); ++i) { int legSquareR = curSquare[0] + legSquareDirs[i][0]; int legSquareC = curSquare[1] + legSquareDirs[i][1]; if(legSquareR >= numRows || legSquareR < 0 || legSquareC >= numCols || legSquareC < 0 ||board[legSquareR][legSquareC] == 0) continue; int newR = curSquare[0] + dirs[i][0]; int newC = curSquare[1] + dirs[i][1]; // check boundary, check the dest square is neither visited(-1) nor blocked (0) if(newR >= numRows || newR < 0 || newC >= numCols || newC < 0 || board[newR][newC] <= 0) continue; // mark visited AT ENQUEUE so each cell is pushed exactly once (no duplicates in the queue) board[newR][newC] = -1; q.emplace(vector({newR, newC})); // alert : q.emplace(5, 10); --> Creates a vector of 5 elements, all initialized to 10 } } return false; } }; int main() { Solution sol; vector start({0,0}); vector target({2,1}); //vector> blocked({{1,0},{0,1}}); vector> blocked; if(sol.isreachable(start, target, blocked)) cout << "True" << endl; else cout << "False" << endl; } /* complexity : same as BFS, O(V+E). When start = (0,0) and target = (9,8), and there is no blocked square. Now there are V=m*n=10*9 = 90 squares/vertices. each square/vertices has 8 edges(8 directions). So O(m*n + 8*m*n) = O(m*n) which is constant as the size of the baord is always 10*9. valid move from (r,c) : r+1->r+2->c+1, r-1->r-1->c+1, r+1->r+2->c-1, r-1->r-1->c-1, c+1->c+2->r+1, c-1->c-1->r+1, c+1->c+2->r-1, c-1->c-1->r-1 answer : not the path or shotest path, ONLY reachable or no t (True or false) BFS : explore(r,c) : try all valid moves and return all dests (r',c') that are NOT a blocker square next : explore each dest from explore(r,c) stop : if (r,c) is Target (before explore(r,c)) 0 1 2 3 4 5 6 7 8 0 S 1 1 1 2 T 3 4 5 6 7 8 9 */ ``` `

Quick Overview

Determine Reachability for a Chinese-Chess Horse with Blocked Legs