이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
vector<vector<int>> a;
char mat[4001][4001];
int comp[4001][4001];
bool viz[16000001];
queue<pair<int, int>> Q;
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
int l;
int Max;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};
bool inside(int i, int j) {
if (i >= 1 && i <= n && j >= 1 && j <= m)
return 1;
return 0;
}
void dfs1(int i, int j) {
int k, inou, jnou;
comp[i][j] = l;
for (k = 0; k < 4; k++) {
inou = i + di[k], jnou = j + dj[k];
if (inside(inou, jnou) && !comp[inou][jnou] && mat[inou][jnou] == mat[i][j])
dfs1(inou, jnou);
}
}
void dfs2(int i, int j) {
int k, inou, jnou;
viz[(i - 1) * m + j] = 1;
for (k = 0; k < 4; k++) {
inou = i + di[k], jnou = j + dj[k];
if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] == mat[i][j])
dfs2(inou, jnou);
else if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] != '.') {
a[comp[i][j]].emplace_back(comp[inou][jnou]);
a[comp[inou][jnou]].emplace_back(comp[i][j]);
}
}
}
void bfs(int x) {
int i;
pair<int, int> p;
Q.push({x, 1});
viz[x] = 1;
while (!Q.empty()) {
p = Q.front();
Q.pop();
if (p.second > Max)
Max = p.second;
for (int x : a[p.first]) {
if (!viz[x]) {
viz[x] = 1;
Q.push({x, p.second + 1});
}
}
}
}
int main() {
fast
int i, j;
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin >> mat[i][j];
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (!comp[i][j] && mat[i][j] != '.') {
l++;
dfs1(i, j);
}
a.resize(l + 1);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (!viz[(i - 1) * m + j] && mat[i][j] != '.')
dfs2(i, j);
for (i = 1; i <= l; i++)
viz[i] = 0;
bfs(1);
cout << Max;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
tracks.cpp: In function 'void bfs(int)':
tracks.cpp:53:9: warning: unused variable 'i' [-Wunused-variable]
53 | int i;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |