PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: negativecode
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
BFS
PROBLEM:
There’s an N\times M grid, each cell of which is either empty or blocked.
Two robots are placed at (1, 1). Every second, both robots must move to an adjacent free cell.
The objective is to make both robots reach (N, M) simultaneously. However, the robots aren’t allowed to be in the same cell (except for (1, 1) and (N, M)).
Find the minimum time needed to achieve this.
EXPLANATION:
If there was only a single robot, the minimum time required is fairly easy to find, and simply equals the length of the shortest path from (1, 1) to (N, M). This can be computed in \mathcal{O}(NM) with a BFS.
Let T denote the minimum time needed for a single robot.
With two robots, T is clearly a lower bound on the answer too.
Note that if (1, 1) and (N, M) are not connected then no valid solution exists either, so we only care about the case where they’re connected.
Let’s check if the answer can be exactly T.
For this, there must be two disjoint paths between (1, 1) and (N, M), so we need to figure out a way to check for this.
How to perform this check?
There are several different ways to do this.
A rather simple one is as follows: find all cells that are on any shortest path from (1, 1) to (N, M).
This can be done using BFS: compute d_1(x, y) to be the shortest path from (1, 1) to (x, y), and d_2(x, y) to be the shortest path from (N, M) to (x, y).
Then, (x, y) lies on some shortest path if and only if d_1(x, y) + d_2(x, y) = d_1(N, M).Once all cells on the shortest path are known, sort them by their distance to (1, 1), i.e., d_1(x, y) values.
Now, if there’s any “level” of the shortest path that contains exactly one cell, every shortest path much pass through this cell and two disjoint paths cannot exist. Otherwise, a valid pair of paths will always exist.There are other solutions too, for example by greedily constructing the paths: this can be seen in the author’s code attached below.
We now know whether the answer can be T or not.
What can we do if it’s not T?
As it turns out, in every other case, either the answer is T+2, or no path exists!
This is because:
- If one of the cells adjacent to (1, 1) is blocked, both robots are forced to make the same move in the very first second, which is forbidden.
- Otherwise, robot 1 can follow the shortest path, while robot 2 can first move away from (1, 1) to the other cell, then move back to (1, 1), and then follow the shortest path itself.
TIME COMPLEXITY:
\mathcal{O}(NM) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define INF 1e17
#define FOR(a, b, c) for (int a = b; a < c; a++)
#define int long long
#define pb push_back
typedef vector <int> vint;
//----------------------DEBUGGER----------------------------------------------------------
#define dbg(x) cout << #x <<" "; _print(x); cout << endl;
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(long double t) {cout << t;}
void _print(double t) {cout << t;}
void _print(unsigned int t) {cout << t;}
template <class T> void _print(vector<vector<T>> v) {for(int j =0;j<v.size();j++){cout <<endl<<"[ "; for (T i : v[j]){_print(i); cout << " ";} cout << "]";};}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.first); cout << ","; _print(p.second); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(vector<vector<vector<T>>> v){for(int k =0;k<v.size();k++){_print(v[k]);}}
//----------------------------------------------------------------------------------------
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void get_path(vector <vint> &dist, vector<pair<int,int>> &path, int mini){
int x = 0, y = 0;
int n = dist.size(), m = dist[0].size();
FOR(i,0,dist[0][0]){
int dis = dist[x][y];
vector <pair<int,int>> cand;
FOR(i,0,4){
int nx = x + dx[i], ny = y + dy[i];
if(nx < n && ny < m && nx >= 0 && ny >= 0 && (dist[nx][ny] == dis-1)){
cand.pb({nx, ny});
}
}
sort(cand.begin(), cand.end());
if(mini == 0){
path.pb(cand.back());
tie(x, y) = cand.back();
}
else{
path.pb(cand[0]);
tie(x, y) = cand[0];
}
}
}
void solve(){
int n, m; cin >> n >> m;
vector <string> grid(n);
vector <vint> visited(n, vint (m)), dist(n, vint(m, INF));
FOR(i,0,n){
cin >> grid[i];
}
queue <pair<pair<int,int>,int>> q;
q.push({{n-1, m-1},0});
dist[n-1][m-1] = 0;
while(!q.empty()){
int x, y;
auto p = q.front(); q.pop();
tie(x, y) = p.first;
int dis = p.second;
if(visited[x][y]) continue;
visited[x][y] = 1;
FOR(i,0,4){
if((x + dx[i] < n) && (y + dy[i] < m) && (x + dx[i] >= 0) && (y + dy[i] >= 0)){
if(!visited[x+dx[i]][y+dy[i]] && grid[x+dx[i]][y+dy[i]] != '#'){
dist[x+dx[i]][y + dy[i]] = dis + 1;
q.push({{x + dx[i], y + dy[i]}, dis + 1});
}
}
}
}
if(dist[0][0] == INF || grid[0][1] == '#' || grid[1][0] == '#'|| grid[n-2][m-1] == '#' || grid[n-1][m-2] == '#' ){
cout << -1 << endl;
return;
}
int ans = dist[0][0] + 2;
vector <pair<int,int>> path1, path2;
get_path(dist, path1, 1);
get_path(dist, path2, 0);
int flag = 2;
FOR(i,0,path1.size()-1){
if(path1[i] == path2[i]) flag = 0;
}
cout << ans - flag << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cout << fixed << setprecision(10);
int t;
cin >> t;
FOR(i,1,t+1){
solve();
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<ll> dx = {-1,1,0,0};
vector<ll> dy = {0,0,-1,1};
void solve(int test_case){
ll n,m; cin >> n >> m;
char a[n+5][m+5];
rep(i,n+5) rep(j,m+5) a[i][j] = '#';
rep1(i,n) rep1(j,m) cin >> a[i][j];
if(a[1][2] == '#' or a[2][1] == '#'){
cout << -1 << endl;
return;
}
if(a[n-1][m] == '#' or a[n][m-1] == '#'){
cout << -1 << endl;
return;
}
ll dis1[n+5][m+5], dis2[n+5][m+5];
memset(dis1,-1,sizeof dis1);
memset(dis2,-1,sizeof dis2);
// dis from (1,1)
{
queue<pll> q;
q.push({1,1});
dis1[1][1] = 0;
while(!q.empty()){
auto [i,j] = q.front();
q.pop();
rep(x,4){
ll i2 = i+dx[x], j2 = j+dy[x];
if(a[i2][j2] == '#') conts;
if(dis1[i2][j2] != -1) conts;
q.push({i2,j2});
dis1[i2][j2] = dis1[i][j]+1;
}
}
}
// dis from (n,m)
{
queue<pll> q;
q.push({n,m});
dis2[n][m] = 0;
while(!q.empty()){
auto [i,j] = q.front();
q.pop();
rep(x,4){
ll i2 = i+dx[x], j2 = j+dy[x];
if(a[i2][j2] == '#') conts;
if(dis2[i2][j2] != -1) conts;
q.push({i2,j2});
dis2[i2][j2] = dis2[i][j]+1;
}
}
}
ll sp = dis1[n][m];
if(sp == -1){
cout << -1 << endl;
return;
}
// find all nodes on the sp
vector<ll> cnt(n*m+5);
rep1(i,n){
rep1(j,m){
if(a[i][j] == '#') conts;
if(dis1[i][j] == -1 or dis2[i][j] == -1) conts;
if(dis1[i][j]+dis2[i][j] == sp){
ll d = dis1[i][j];
cnt[d]++;
}
}
}
ll ans = sp;
rep1(i,sp-1){
if(cnt[i] == 1){
ans = sp+2;
break;
}
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}