제출 #441340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441340		HadiHosseini	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	433 ms	126216 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
const int N = 4001; 
const int M = 4001;
int n, m;
char a[N][M]; 
int d[N][M];
int ans = 1;
bool visited[N][M];
 
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];
 	}
 }
 
 deque<pair<int, int>> q;
 visited[0][0] = true;
 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) && !visited[x][y]){
 	   if(a[node.first][node.second] == a[x][y]){
 	   	d[x][y] = d[node.first][node.second];
 	   	q.push_front({x, y});
 	   	visited[x][y] = true;
 	   }
 	   else {
 	   	d[x][y] = d[node.first][node.second] + 1;
 	   	q.push_back({x, y});
 	   	visited[x][y] = true;
 	   }
 	 }
 	}
 }
 
 cout << ans << "\n";
 
 
 
	return 0;
} 

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