Блог пользователя karthikeyan_01

Автор karthikeyan_01, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It would most likely timeout.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.