이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
vector<vector<char>> field;
int h, w, answer = 1;
vector<int> father, chainSize, turn, put;
vector<vector<pair<int, int>>> points;
int find(int n)
{
if(father[n] != n)
father[n] = find(father[n]);
return father[n];
}
void join(int a, int b)
{
a = find(a);
b = find(b);
if(a == b)
return;
if(chainSize[a] < chainSize[b])
swap(a, b);
father[b] = a;
chainSize[a] += chainSize[b];
}
int main()
{
scanf("%d %d", &h, &w);
field.assign(h, vector<char>(w));
father.assign(h*w, 0);
chainSize.assign(h*w, 1);
turn.assign(h*w, 0);
points.assign(h*w, vector<pair<int, int>>());
put.assign(h*w, 0);
for(int i = 0; i < h; i++)
{
for(int j = 0; j < w; j++)
{
scanf(" %c", &field[i][j]);
father[i*w + j] = i*w + j;
if(field[i][j] == '.')
continue;
if(i != 0)
{
if(field[i - 1][j] == field[i][j])
join(i*w + j, (i - 1)*w + j);
}
if(j != 0)
{
if(field[i][j - 1] == field[i][j])
join(i*w + j, i*w + j - 1);
}
}
}
for(int i = 0; i < h; i++)
{
for(int j = 0; j < w; j++)
points[find(i*w + j)].push_back(make_pair(i, j));
}
turn[find(0)] = 1;
queue<int> q;
q.push(find(0));
put[find(0)] = 1;
while(!q.empty())
{
int cur = q.front();
answer = max(answer, turn[cur]);
for(int i = 0; i < points[cur].size(); i++)
{
int a = points[cur][i].first;
int b = points[cur][i].second;
if(a != 0)
{
if(field[a - 1][b] != '.' && find((a - 1)*w + b) != cur)
{
if(!put[find((a - 1)*w + b)])
{
turn[find((a - 1)*w + b)] = turn[cur] + 1;
q.push(find((a - 1)*w + b));
put[find((a - 1)*w + b)] = 1;
}
}
}
if(b != 0)
{
if(field[a][b - 1] != '.' && find(a*w + b - 1) != cur)
{
if(!put[find(a*w + b - 1)])
{
turn[find(a*w + b - 1)] = turn[cur] + 1;
q.push(find(a*w + b - 1));
put[find(a*w + b - 1)] = 1;
}
}
}
if(a != h - 1)
{
if(field[a + 1][b] != '.' && find((a + 1)*w + b) != cur)
{
if(!put[find((a + 1)*w + b)])
{
turn[find((a + 1)*w + b)] = turn[cur] + 1;
q.push(find((a + 1)*w + b));
put[find((a + 1)*w + b)] = 1;
}
}
}
if(b != w - 1)
{
if(field[a][b + 1] != '.' && find(a*w + b + 1) != cur)
{
if(!put[find(a*w + b + 1)])
{
turn[find(a*w + b + 1)] = turn[cur] + 1;
q.push(find(a*w + b + 1));
put[find(a*w + b + 1)] = 1;
}
}
}
}
points[cur].erase(points[cur].begin(), points[cur].end());
q.pop();
}
printf("%d\n", answer);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
tracks.cpp: In function 'int main()':
tracks.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < points[cur].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
tracks.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d %d", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf(" %c", &field[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |