A BFS problem which needs maintain two players location info

As we now that BFS can solve shortest path problem. Today I had a nice question in the ABC contest from atcoder. It is the problem D. For this problem, we can use the standard BFS with slighly modification:

maintain two player’s location info.

As we need two player’s info, the time and space complexity will be

O(n⁴)

Problem

D — Synchronized Player

Code in C++

#include<iostream>                                                                      
#include<vector>                                                                        
#include<cstring>                                                                       
using namespace std;                                                                    
const int N = 65;                                                                       
int mask[N][N][N][N];                                                                   
typedef pair<int, int> PII;                                                             
bool invalid(int i, int j,  vector<string>&grid, int n){                                
    if (i == 0 || j ==0  || i == n +1 || j == n +1 || grid[--i][--j] == '#')return true;
    return false;                                                                       
}                                                                                       
int bfs(int i1, int j1, int i2, int j2, vector<string>& grid, int n){                   
    vector<pair<PII, PII>> curr_level;                                                  
    vector<PII> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};                                 
    curr_level.emplace_back(make_pair(i1, j1), make_pair(i2, j2));                      
    int level = 0;                                                                      
    int r1, r2, c1, c2;                                                                 
    while (!curr_level.empty()){                                                        
                                                                                        
        vector<pair<PII, PII>> next_level;                                              
        for (auto [ij1, ij2]: curr_level){                                              
            auto [i1, j1] = ij1;                                                        
            auto [i2, j2] = ij2;                                                        
            for (auto [di, dj]: dirs){                                                  
                r1 = i1 + di;                                                           
                c1 = j1 + dj;                                                           
                r2 = i2 + di;                                                           
                c2 = j2 + dj;                                                           
                if (invalid(r1, c1, grid, n)){                                          
                    r1 = i1;                                                            
                    c1 = j1;                                                            
                }                                                                       
                if (invalid(r2, c2, grid, n)){                                          
                    r2 = i2;                                                            
                    c2 = j2;                                                            
                }                                                                       
                if (r1 == r2 && c1 == c2)return level + 1;                              
                if (mask[r1][c1][r2][c2])continue;                                      
                mask[r1][c1][r2][c2] = 1;                                               
                next_level.emplace_back(make_pair(r1, c1), make_pair(r2, c2));          
            }                                                                           
        }                                                                               
        level++;                                                                        
        curr_level = next_level;                                                        
    }                                                                                   
    return -1;                                                                          
}                                                                                       
int main(){                                                                             
    memset(mask, 0, sizeof mask);                                                       
    int n; cin >> n;                                                                    
    int i1=-1, j1=-1, i2=-1, j2 =-1;                                                    
    vector<string> grid(n);                                                             
    for (int i = 0; i < n; ++i){                                                        
        cin >> grid[i];                                                                 
        for (int j = 0; j < n; ++j){                                                    
            if (grid[i][j] == 'P'){                                                     
                if (i1 == -1){                                                          
                    i1 = i + 1;                                                         
                    j1 = j + 1;                                                         
                }else{                                                                  
                    i2 = i + 1;                                                         
                    j2 = j + 1;                                                         
                }                                                                       
            }                                                                           
        }                                                                               
    }                                                                                   
    mask[i1][j1][i2][j2] = 1;                                                           
    auto ret = bfs(i1, j1, i2, j2, grid, n);                                            
    cout << ret << endl;                                                                
    return 0;                                                                           
}   

The code is very standard BFS. Using this code can solve the problem smoothly!

Happy coding!