이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include<algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 5e3 + 111;
const int MOD = 1e9 + 7;
const int N = 1e6;
using ll = long long;
int d_x[]{ 0,0,-1,1 };
int d_y[]{ 1,-1,0,0 };
int h, w;
char t[MAXN][MAXN];
int dist[MAXN][MAXN];
bool vis[MAXN][MAXN];
int ans;
void bfs(int x, int y)
{
deque<pair<int, int>> q;
q.push_back({ x,y });
vis[x][y] = true;
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
dist[i][j] = 1e9;
dist[0][0] = 0;
while (!q.empty())
{
int curr_x = q.front().first;
int curr_y = q.front().second;
q.pop_front();
for (int d = 0; d < 4; d++)
{
int newX = d_x[d] + curr_x;
int newY = d_y[d] + curr_y;
if (newX >= 0 && newY >= 0 && newX < h && newY < w && t[newX][newY] != '.')
{
int w = (t[newX][newY] != t[curr_x][curr_y]);
if (dist[newX][newY] > dist[curr_x][curr_y] + w)
{
dist[newX][newY] = dist[curr_x][curr_y] + w;
ans = max(dist[newX][newY], ans);
if (w == 1)
q.push_back({ newX,newY });
else
q.push_front({ newX,newY });
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("threesum.in", "r", stdin);
//freopen("threesum.out", "w", stdout);
cin >> h >> w;
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
cin >> t[i][j];
bfs(0, 0);
cout << ans + 1<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |