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

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

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
  • Проголосовать: не нравится

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

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

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

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

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

    It would most likely timeout.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 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