fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int INF = 1e9;
  7.  
  8. // ĐỂ MẢNG Ở ĐÂY: Khai báo mảng tĩnh toàn cục tối đa 1005 x 1005 để không bị tràn bộ nhớ
  9. int n, m;
  10. int a[1005][1005];
  11. int F[1005][1005]; // F[i][j] lưu chi phí nhỏ nhất từ ô (i, j) ra biên
  12.  
  13. int main() {
  14.     // Tối ưu tốc độ nhập xuất cho mảng lớn
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(NULL);
  17.  
  18.     int startX, startY;
  19.     if (!(cin >> n >> m >> startX >> startY)) return 0;
  20.  
  21.     // Nhập ma trận
  22.     for (int i = 0; i < n; i++) {
  23.         for (int j = 0; j < m; j++) {
  24.             cin >> a[i][j];
  25.             F[i][j] = INF; // Ban đầu coi như mọi ô đều chưa có đường ra biên
  26.         }
  27.     }
  28.  
  29.     // Bước 1: Những ô nằm ở biên thì chi phí ra biên bằng chính nó
  30.     for (int i = 0; i < n; i++) {
  31.         for (int j = 0; j < m; j++) {
  32.             if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
  33.                 F[i][j] = a[i][j];
  34.             }
  35.         }
  36.     }
  37.  
  38.     // Bước 2: Vòng lặp cập nhật loang bảng số (Co bóp ma trận)
  39.     // Với N, M <= 1000, lặp tối đa khoảng 10-20 lần là ma trận ổn định và tối ưu xong
  40.     for (int lan = 0; lan < 20; lan++) { 
  41.         for (int i = 1; i < n - 1; i++) {
  42.             for (int j = 1; j < m - 1; j++) {
  43.                 // Lấy ô có chi phí nhỏ nhất trong 4 hướng xung quanh
  44.                 int minXungQuanh = min({F[i-1][j], F[i+1][j], F[i][j-1], F[i][j+1]});
  45.  
  46.                 // Nếu tìm được đường đi qua hàng xóm tốt hơn đường cũ, cập nhật lại
  47.                 if (minXungQuanh != INF && a[i][j] + minXungQuanh < F[i][j]) {
  48.                     F[i][j] = a[i][j] + minXungQuanh;
  49.                 }
  50.             }
  51.         }
  52.     }
  53.  
  54.     // Bước 3: In ra chi phí tại ô xuất phát
  55.     cout << F[startX][startY] << "\n";
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fjfsTG
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!