Problem State : https://cses.fi/problemset/task/1193
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define DB(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).begin() , (x).end()
using namespace std;
const int maxN = 1e3;
char mat[maxN][maxN];
bool vis[maxN][maxN];
pair<int ,int > source;
int n, m ;
int dx[4] = {-1 , 0 , 1 , 0};
int dy[4] = {0, 1, 0 , -1 };
pair<int ,int > dest;
bool isok(int xx , int yy){
if( xx >=0 && yy >=0 && xx <n && yy < m && mat[xx][yy] == '.' && !vis[xx][yy]){
return true;
}
return false;
}
vector<char> pos;
int ct =0;
void bfs(){
queue<pair<int, int>> q;
q.push(source);
int ans =0;
while(!q.empty()){
pair<int , int> dd = q.front();
q.pop();
vis[dd.fi][dd.se] = true;
for(int i =0; i<4; ++i){
if(mat[dd.fi+ dx[i]][dd.se+dy[i]] == 'B'){
ans= 1;
break;
}
if(isok(dd.fi + dx[i] , dd.se + dy[i])){
q.push({dd.fi + dx[i] , dd.se + dy[i]});
ct++;
}
}
if(ans){
cout << "YES" << "\n";
cout << ct << "\n";
break;
}
}
}
int32_t main(){
IOS;
cin >>n >>m;
for(int i =0; i<n; ++i){
for(int j =0; j<m; ++j){
cin >> mat[i][j];
}
}
memset(vis , false , sizeof(vis));
for(int i =0; i<n; ++i){
for(int j =0; j<m; ++j){
if( mat[i][j] == 'A'){
source = {i , j};
}
if(mat[i][j] == 'B'){
dest = {i , j};
}
}
}
bfs();
return 0;
}
o.p YES 11
but the output should be 9 , How to solve this
ct
shows the number of nodes visited, not the level of the node.And
if(mat[dd.fi+ dx[i]][dd.se+dy[i]] == 'B'){...
is out of bounds.May I know if this question can be solved using dfs?
It would most likely timeout.
I tried to use bfs. It can pass all of the test cases but one with TLE. Any idea to optimize further? The maze is 999x999 and the answer has 499998 characters.
You are copying the path in every step, which is a lot of time consuming copy operations.
Instead build a distance map, and once found the distance to last position (ie every cell on a path to last position), backtrack the path.
Thanks a lot. Finally solved it. Appreciate your help!