Submission #441343

#	Time	Username	Problem	Language	Result	Execution time	Memory
441343		HadiHosseini	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	578 ms	118996 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
const int N = 4000; 
const int M = 4000;
int n, m;
char a[N][M]; 
int d[N][M];
int ans = 1;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
 
bool inside(int r, int c) {
	if (r < 0 || r > n || c < 0 || c > m) return false;
	if (a[r][c] == '.') return false;
	return true; 
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
 
 cin >> n >> m;
 for(int i = 0 ; i < n; i++){
 	string s; cin >> s;
 	for(int j = 0 ; j < m; j++){
 		 a[i][j] = s[j];
 	}
 }

 n--; m--;
 
 deque<pair<int, int>> q;
 q.push_back({0, 0});
 d[0][0] = 1;
 while(!q.empty()){
 	auto node = q.front();
 	q.pop_front();
 	ans = max(ans, d[node.first][node.second]);
 	for(int i = 0 ; i < 4; i++){
 	 int x = node.first + dx[i]; int y = node.second + dy[i];
 	 if(inside(x, y) && d[x][y] == 0){
 	   if(a[node.first][node.second] == a[x][y]){
 	   	d[x][y] = d[node.first][node.second];
 	   	q.push_front({x, y});
 	   }
 	   else {
 	   	d[x][y] = d[node.first][node.second] + 1;
 	   	q.push_back({x, y});
 	   }
 	 }
 	}
 }
 
 cout << ans << "\n";
 
 
 
	return 0;
} 

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70