karthikeyan_01's blog

By karthikeyan_01, history, 4 years ago, In English

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

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

ct shows the number of nodes visited, not the level of the node.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And if(mat[dd.fi+ dx[i]][dd.se+dy[i]] == 'B'){... is out of bounds.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May I know if this question can be solved using dfs?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would most likely timeout.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      code
      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thanks a lot. Finally solved it. Appreciate your help!