#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MAXN 1000005
int R, C, no = 1, ans = 1;
vector<vector<int>> mark(1005, vector<int>(1005, -1));
vector<vector<int>> graph;
vector<int> delRow = {-1, 0, 0, 1};
vector<int> delCol = {0, -1, 1, 0};
vector<vector<char>> grid;
bool vis[1005][1005];
bool check(int row, int col) {
if (row <= 0 || row > R || col <= 0 || col > C)
return false;
return true;
}
void addEdge(int from, int to) {
for (auto u : graph[from])
if (u == to)
return ;
graph[from].push_back(to);
graph[to].push_back(from);
}
void dfs(int i, int j) {
vis[i][j] = true;
mark[i][j] = no;
for (int q = 0; q < 4; q++) {
int nRow = i + delRow[q];
int nCol = j + delCol[q];
if (check(nRow, nCol) && grid[nRow][nCol] == grid[i][j] && !vis[nRow][nCol])
dfs(nRow, nCol);
}
}
void dfs2(int i, int j) {
vis[i][j] = true;
for (int q = 0; q < 4; q++) {
int nRow = i + delRow[q];
int nCol = j + delCol[q];
if (!check(nRow, nCol) || grid[nRow][nCol] == '*')
continue;
int from = mark[i][j];
int to = mark[nRow][nCol];
if (from != to)
addEdge(from, to);
if (!vis[nRow][nCol])
dfs2(nRow, nCol);
}
}
void bfs(int node) {
vector<int> vis(no+1, false);
queue<pair<int,int>> q;
q.push({node, 1});
while (!q.empty()) {
int node = q.front().first;
int dist = q.front().second;
q.pop();
ans = max(ans, dist);
if (vis[node])
continue;
vis[node] = true;
for (auto u : graph[node]) {
if (!vis[u])
q.push({u, dist+1});
}
}
}
int main() {
fast
memset(vis, false, sizeof(vis));
string s;
cin >> R >> C;
grid = vector<vector<char>>(R+1, vector<char>(C+1));
for (int i = 1; i <= R; i++) {
cin >> s;
for (int j = 1; j <= C; j++)
grid[i][j] = s[j-1];
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (!vis[i][j] && grid[i][j] != '*') {
dfs(i, j);
no++;
}
}
}
graph = vector<vector<int>>(no+1, vector<int>(0));
memset(vis, false, sizeof(vis));
dfs2(1, 1);
bfs(1);
cout << ans << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5204 KB |
Output is correct |
2 |
Correct |
3 ms |
5204 KB |
Output is correct |
3 |
Correct |
3 ms |
5204 KB |
Output is correct |
4 |
Correct |
4 ms |
5332 KB |
Output is correct |
5 |
Correct |
3 ms |
5568 KB |
Output is correct |
6 |
Correct |
3 ms |
5716 KB |
Output is correct |
7 |
Correct |
3 ms |
5716 KB |
Output is correct |
8 |
Correct |
3 ms |
5588 KB |
Output is correct |
9 |
Correct |
3 ms |
5556 KB |
Output is correct |
10 |
Correct |
4 ms |
5660 KB |
Output is correct |
11 |
Correct |
3 ms |
5588 KB |
Output is correct |
12 |
Correct |
4 ms |
5716 KB |
Output is correct |
13 |
Correct |
5 ms |
5564 KB |
Output is correct |
14 |
Correct |
5 ms |
5588 KB |
Output is correct |
15 |
Correct |
3 ms |
5588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5204 KB |
Output is correct |
2 |
Correct |
3 ms |
5204 KB |
Output is correct |
3 |
Correct |
3 ms |
5204 KB |
Output is correct |
4 |
Correct |
4 ms |
5332 KB |
Output is correct |
5 |
Correct |
3 ms |
5568 KB |
Output is correct |
6 |
Correct |
3 ms |
5716 KB |
Output is correct |
7 |
Correct |
3 ms |
5716 KB |
Output is correct |
8 |
Correct |
3 ms |
5588 KB |
Output is correct |
9 |
Correct |
3 ms |
5556 KB |
Output is correct |
10 |
Correct |
4 ms |
5660 KB |
Output is correct |
11 |
Correct |
3 ms |
5588 KB |
Output is correct |
12 |
Correct |
4 ms |
5716 KB |
Output is correct |
13 |
Correct |
5 ms |
5564 KB |
Output is correct |
14 |
Correct |
5 ms |
5588 KB |
Output is correct |
15 |
Correct |
3 ms |
5588 KB |
Output is correct |
16 |
Correct |
20 ms |
11744 KB |
Output is correct |
17 |
Correct |
20 ms |
12264 KB |
Output is correct |
18 |
Correct |
17 ms |
11972 KB |
Output is correct |
19 |
Correct |
25 ms |
13524 KB |
Output is correct |
20 |
Correct |
22 ms |
11856 KB |
Output is correct |
21 |
Correct |
139 ms |
44236 KB |
Output is correct |
22 |
Correct |
116 ms |
44412 KB |
Output is correct |
23 |
Correct |
125 ms |
45004 KB |
Output is correct |
24 |
Correct |
121 ms |
46368 KB |
Output is correct |
25 |
Correct |
119 ms |
45412 KB |
Output is correct |
26 |
Correct |
117 ms |
45160 KB |
Output is correct |
27 |
Correct |
123 ms |
44568 KB |
Output is correct |
28 |
Correct |
132 ms |
44476 KB |
Output is correct |
29 |
Correct |
121 ms |
46532 KB |
Output is correct |
30 |
Correct |
119 ms |
45708 KB |
Output is correct |