#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e3 + 5;
int n, m;
char a[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
array<int, 2> FindPipe(int x, int y, int next_dir)
{
array<int, 2> prev_pos = {x, y};
x += dx[next_dir];
y += dy[next_dir];
int _x, _y;
while(true)
{
// cout << "x = " << x << ", y = " << y << endl;
// cout << "prev_pos = {" << prev_pos[0] << ", " << prev_pos[1] << "}" << endl;
int cnt = 0;
for(int i = 0; i < 4; i++)
{
if(x + dx[i] <= 0 || x + dx[i] > n || y + dy[i] <= 0 || y + dy[i] > m)
{
continue;
}
if(a[x + dx[i]][y + dy[i]] == '-' || a[x + dx[i]][y + dy[i]] == '|' || a[x + dx[i]][y + dy[i]] == '+')
{
cnt++;
}
}
// cout << "cnt = " << cnt << endl;
if(cnt >= 3)
{
_x = x, _y = y;
break;
}
for(int i = 0; i < 4; i++)
{
// cout << x + dx[i] << ", " << y + dy[i] << endl;
if(x + dx[i] <= 0 || x + dx[i] > n || y + dy[i] <= 0 || y + dy[i] > m)
{
continue;
}
// cout << "hello" << endl;
if(a[x + dx[i]][y + dy[i]] != '.' && (x + dx[i] != prev_pos[0] || y + dy[i] != prev_pos[1]))
{
prev_pos = {x, y};
x += dx[i], y += dy[i];
break;
}
}
}
while(a[_x][_y] != '+')
{
_y--;
}
return {_x, _y};
}
void Component(int _i, int _j, int parent)
{
// cout << "Component(" << _i << " " << _j << ") -> " << parent << endl;
int pos_x = 0, pos_y;
// Finding top left and bottom right corner of the rectangle component
for(int j = _j + 1; j <= m; j++)
{
if(a[_i][j] == '+')
{
pos_y = j;
break;
}
}
assert(pos_y != 0);
for(int i = _i + 1; i <= n; i++)
{
if(a[i][pos_y] == '+')
{
pos_x = i;
break;
}
}
assert(pos_x != 0);
// cout << "pos_x = " << pos_x << ", pos_y = " << pos_y << endl;
// component top left: (_i, _j)
// component bottom right: (pos_x, pos_y)
// Finding the number of the rectangle component
int current_number = 0;
for(int i = _i; i <= pos_x; i++)
{
for(int j = _j; j <= pos_y; j++)
{
if(a[i][j] >= '0' && a[i][j] <= '9')
{
current_number = (current_number * 10) + (a[i][j] - '0');
}
}
}
// cout << "current_number = " << current_number << endl;
assert(current_number != 0);
// Finding pipes (if any) connected to the component, and the components to which the pipe leads to
for(int i = pos_x; i >= _i; i--)
{
if(_j != 0 && a[i][_j - 1] == '-')
{
// cout << "Found at (left hand side) pos: (" << i << ", " << _j << ") " << endl;
array<int, 2> top_left = FindPipe(i, _j, 3);
Component(top_left[0], top_left[1], current_number);
}
if(pos_y != m && a[i][pos_y + 1] == '-')
{
// cout << "Found at (right hand side) pos: (" << i << ", " << pos_y << ") " << endl;
array<int, 2> top_left = FindPipe(i, pos_y, 1);
Component(top_left[0], top_left[1], current_number);
}
}
cout << current_number << "\n";
}
void Solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
bool flag = false;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == '+')
{
Component(i, j, 0);
flag = true;
break;
}
}
if(flag == true)
{
break;
}
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
clickbait.cpp: In function 'void Component(long long int, long long int, long long int)':
clickbait.cpp:115:3: warning: 'pos_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
115 | if(pos_y != m && a[i][pos_y + 1] == '-')
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
2 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
20 ms |
2244 KB |
Output is correct |
