#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
const ll INF = 1e9 + 7;
bool is_valid(int x, int y, int n, int m)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
void solve()
{
int H, W;
cin >> H >> W;
vector<string> a(H);
for (int i = 0; i < H; i++)
{
cin >> a[i];
}
deque<pair<int, int>> q;
vector<vector<int>>dis(H, vector<int>(W, INF));
int ans = 1;
q.push_front({0, 0});
dis[0][0] = 1;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop_front();
int del_x[4] = {-1, 0, 0, 1};
int del_y[4] = {0, -1, 1, 0};
for (int i = 0; i < 4; i++)
{
int new_x = x + del_x[i];
int new_y = y + del_y[i];
if (is_valid(new_x, new_y, H, W) && a[new_x][new_y] != '.')
{
if (a[new_x][new_y] == a[x][y] && dis[new_x][new_y] > dis[x][y])
{
dis[new_x][new_y] = dis[x][y];
q.push_front({new_x, new_y});
}
else if (a[new_x][new_y] != a[x][y] && dis[new_x][new_y] > dis[x][y] + 1)
{
dis[new_x][new_y] = dis[x][y] + 1;
q.push_back({new_x, new_y});
}
}
}
}
cout << dis[H - 1][W - 1] + 1<< endl;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while (t--)
{
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |