Untitled
unknown
plain_text
a year ago
2.0 kB
4
Indexable
#include <iostream> #include <utility> using namespace std; const int MAX_N = 30; const int MAX_M = MAX_N * MAX_N; // Tính khoảng cách ngắn nhất từ start đến ground int shortestPath(int grid[MAX_N][MAX_N], pair<int, int> start, int N) { int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; pair<pair<int, int>, int> q[MAX_M]; int front = 0, rear = 0; q[rear++] = {start, 0}; bool visited[MAX_N][MAX_N] = {false}; visited[start.first][start.second] = true; while (front < rear) { auto frontNode = q[front++]; int x = frontNode.first.first; int y = frontNode.first.second; int dist = frontNode.second; if (grid[x][y] == 0) { return dist; } for (int i = 0; i < 4; ++i) { int nx = x + directions[i][0]; int ny = y + directions[i][1]; if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) { visited[nx][ny] = true; q[rear++] = {{nx, ny}, dist + 1}; } } } return -1; // Không thể đạt được mặt đất } // Tìm số lượng cm khối đất ít nhất cần đào để thoát khỏi khối đất int minDiggingNeeded(int grid[MAX_N][MAX_N], int N) { pair<int, int> start; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (grid[i][j] == 2) { start = {i, j}; break; } } } int minDigging = INT_MAX; minDigging = min(minDigging, shortestPath(grid, start, N)); return minDigging; } int main() { int T; cin >> T; for (int t = 1; t <= T; ++t) { int N; cin >> N; int grid[MAX_N][MAX_N]; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cin >> grid[i][j]; } } int minDigging = minDiggingNeeded(grid, N); cout << "#" << t << " " << minDigging << endl; } return 0; }
Editor is loading...
Leave a Comment