fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> findOptimalPair(int n, int m, vector<vector<int>> blockedPositions) {
  5.     vector<vector<int>> dist(n, vector<int>(m, -1));
  6.     vector<vector<int>> blocked(n, vector<int>(m, 0));
  7.  
  8.     queue<pair<int,int>> q;
  9.  
  10.     for (auto &b : blockedPositions) {
  11.         int x = b[0] - 1;
  12.         int y = b[1] - 1;
  13.         blocked[x][y] = 1;
  14.         dist[x][y] = 0;
  15.         q.push({x, y});
  16.     }
  17.  
  18.     int dx[4] = {-1,1,0,0};
  19.     int dy[4] = {0,0,-1,1};
  20.  
  21.     // Multi-source BFS computes exact Manhattan distance
  22.     while (!q.empty()) {
  23.         auto [x,y] = q.front();
  24.         q.pop();
  25.  
  26.         for (int k=0;k<4;k++) {
  27.             int nx=x+dx[k];
  28.             int ny=y+dy[k];
  29.  
  30.             if(nx<0||nx>=n||ny<0||ny>=m) continue;
  31.             if(dist[nx][ny]!=-1) continue;
  32.  
  33.             dist[nx][ny]=dist[x][y]+1;
  34.             q.push({nx,ny});
  35.         }
  36.     }
  37.  
  38.     auto check = [&](int limit)->int{
  39.  
  40.         if(blocked[0][0] || blocked[n-1][m-1])
  41.             return -1;
  42.  
  43.         if(dist[0][0] < limit || dist[n-1][m-1] < limit)
  44.             return -1;
  45.  
  46.         vector<vector<int>> d(n, vector<int>(m,-1));
  47.  
  48.         queue<pair<int,int>> qq;
  49.         qq.push({0,0});
  50.         d[0][0]=0;
  51.  
  52.         while(!qq.empty()){
  53.  
  54.             auto [x,y]=qq.front();
  55.             qq.pop();
  56.  
  57.             for(int k=0;k<4;k++){
  58.  
  59.                 int nx=x+dx[k];
  60.                 int ny=y+dy[k];
  61.  
  62.                 if(nx<0||nx>=n||ny<0||ny>=m)
  63.                     continue;
  64.  
  65.                 if(blocked[nx][ny])
  66.                     continue;
  67.  
  68.                 if(dist[nx][ny] < limit)
  69.                     continue;
  70.  
  71.                 if(d[nx][ny]!=-1)
  72.                     continue;
  73.  
  74.                 d[nx][ny]=d[x][y]+1;
  75.                 qq.push({nx,ny});
  76.             }
  77.         }
  78.  
  79.         if(d[n-1][m-1]==-1)
  80.             return -1;
  81.  
  82.         return d[n-1][m-1]+1;
  83.     };
  84.  
  85.     int hi=min(dist[0][0], dist[n-1][m-1]);
  86.     int lo=0;
  87.     int best=-1;
  88.  
  89.     while(lo<=hi){
  90.  
  91.         int mid=(lo+hi)/2;
  92.  
  93.         if(check(mid)!=-1){
  94.             best=mid;
  95.             lo=mid+1;
  96.         }else{
  97.             hi=mid-1;
  98.         }
  99.     }
  100.  
  101.     if(best==-1)
  102.         return {-1,-1};
  103.  
  104.     return {best, check(best)};
  105. }
  106.  
  107. int main() {
  108.     // Test Case from the prompt description
  109.     int n = 4;
  110.     int m = 3;
  111.     vector<vector<int>> blockedPositions = {{1, 3}, {2, 3}};
  112.  
  113.     // int n = 3;
  114.     // int m = 3;
  115.     // vector<vector<int>> blockedPositions = {{1, 2}, {2, 1}, {2, 2}};
  116.  
  117.     // int n = 4;
  118.     // int m = 4;
  119.     // vector<vector<int>> blockedPositions = {{1, 2}, {4, 3}};
  120.  
  121.     vector<int> result = findOptimalPair(n, m, blockedPositions);
  122.  
  123.     cout << "Maximum Strength: " << result[0] << endl;
  124.     cout << "Minimum Cells Visited: " << result[1] << endl;
  125.  
  126.     // Expected Output:
  127.     // Maximum Strength: 2
  128.     // Minimum Cells Visited: 6
  129.  
  130.     return 0;
  131. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum Strength: 2
Minimum Cells Visited: 6
https://ideone.com/uGK2C0
language:
C++14 (gcc 8.3)
created:
5 hours 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!