#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
#define F first
#define S second
const double eps = 1e-9;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()){cout << v[i] << " ";}
cout << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
void setIO(string name = "") {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
void init_code(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
void solve(){
// store very big numbers may mean log2
ll h,w;
cin >> h >> w;
vector<string> grid(h);
FOR(i,0,h) cin >> grid[i];
vector<vll> dist(h,vll(w,INT_MAX));
dist[0][0] = 1;
deque<pll> d;
vector<vector<bool>> visited(h,vector<bool>(w,false));
d.push_front({0,0});
while(!d.empty()){
pll curr = d.front();
d.pop_front();
if(grid[curr.F][curr.S]=='.') continue;
if(visited[curr.F][curr.S]) continue;
visited[curr.F][curr.S] = true;
if(curr.F>0){
ll alt = dist[curr.F][curr.S];
ll wt = 0;
if(grid[curr.F][curr.S]!=grid[curr.F-1][curr.S]) wt++;
if((alt+wt)<dist[curr.F-1][curr.S]){
dist[curr.F-1][curr.S] = alt+wt;
if(wt==0){
d.push_front({curr.F-1,curr.S});
}
else{
d.push_back({curr.F-1,curr.S});
}
}
}
if(curr.S>0){
ll alt = dist[curr.F][curr.S];
ll wt = 0;
if(grid[curr.F][curr.S]!=grid[curr.F][curr.S-1]) wt++;
if((alt+wt)<dist[curr.F][curr.S-1]){
dist[curr.F][curr.S-1] = alt+wt;
if(wt==0){
d.push_front({curr.F,curr.S-1});
}
else{
d.push_back({curr.F,curr.S-1});
}
}
}
if(curr.F<(h-1)){
ll alt = dist[curr.F][curr.S];
ll wt = 0;
if(grid[curr.F][curr.S]!=grid[curr.F+1][curr.S]) wt++;
if((alt+wt)<dist[curr.F+1][curr.S]){
dist[curr.F+1][curr.S] = alt+wt;
if(wt==0){
d.push_front({curr.F+1,curr.S});
}
else{
d.push_back({curr.F+1,curr.S});
}
}
}
if(curr.S<(w-1)){
ll alt = dist[curr.F][curr.S];
ll wt = 0;
if(grid[curr.F][curr.S]!=grid[curr.F][curr.S+1]) wt++;
if((alt+wt)<dist[curr.F][curr.S+1]){
dist[curr.F][curr.S+1] = alt+wt;
if(wt==0){
d.push_front({curr.F,curr.S+1});
}
else{
d.push_back({curr.F,curr.S+1});
}
}
}
}
ll ans = 0;
FOR(i,0,h){
FOR(j,0,w){
if(grid[i][j]=='.') continue;
ans = max(ans,dist[i][j]);
}
}
cout << ans << "\n";
}
signed main(){
//setIO
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// init_code();
ll t=1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp: In function 'void init_code()':
tracks.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |