You are viewing a single comment's thread. Return to all comments →
simply O(n^3) algo
void update(int I, int J, int i, int j, vector<vector<bool>>& visited, vector<vector<int>>& minPath, queue<pair<int, int>>& Q) { if (visited[i][j]) return; visited[i][j] = true; minPath[i][j] = minPath[I][J] + 1; Q.push(make_pair(i, j)); return; } int minimumMoves(int n, vector<vector<char>> grid, int startX, int startY, int goalX, int goalY) { vector<vector<bool>> visited(n + 2, vector<bool>(n + 2)); vector<vector<int>> minPath(n + 2, vector<int>(n + 2, -1)); queue<pair<int, int>> Q; Q.push(make_pair(startX, startY)); visited[startX][startY] = true; minPath[startX][startY] = 0; while (!Q.empty()) { int I = Q.front().first, J = Q.front().second; for (int i=1; I - i > 0; i++) { if (grid[I-i][J] == 'X') break; update(I, J, I-i, J, visited, minPath, Q); } for (int i=1; I + i < n+1; i++) { if (grid[I+i][J] == 'X') break; update(I, J, I+i, J, visited, minPath, Q); } for (int j=1; J - j > 0; j++) { if (grid[I][J-j] == 'X') break; update(I, J, I, J-j, visited, minPath, Q); } for (int j=1; J + j < n+1; j++) { if (grid[I][J+j] == 'X') break; update(I, J, I, J+j, visited, minPath, Q); } Q.pop(); } return minPath[goalX][goalY]; } int main() { int n, startX, startY, goalX, goalY; string s; cin >> n; vector<vector<char>> grid(n + 2, vector<char>(n + 2)); for (int i = 1; i <= n; i++) { cin >> s; for (int j = 1; j <= n; j++) grid[i][j] = s[j - 1]; } cin >> startX >> startY >> goalX >> goalY; cout << minimumMoves(n, grid, startX + 1, startY + 1, goalX + 1, goalY + 1); }
Seems like cookies are disabled on this browser, please enable them to open this website
Castle on the Grid
You are viewing a single comment's thread. Return to all comments →
simply O(n^3) algo