This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const int MAXN = 4000;
char mat[MAXN + 1][MAXN + 1];
int sef[MAXN * MAXN + 1];
int myfind(int x) {
if(sef[x] == 0)
return x;
return sef[x] = myfind(sef[x]);
}
inline void myunion(int x, int y) {
x = myfind(x), y = myfind(y);
if(x != y) {
sef[x] = y;
}
}
bool vis[MAXN * MAXN + 1];
char dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
int n, m;
inline bool in(int l, int c) {
return 1 <= l && l <= n && 1 <= c && c <= m;
}
inline int get(int l, int c) {
return (l - 1) * m + c;
}
inline int solve(char ch) {
int i, j;
memset(sef, 0, sizeof(sef));
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(mat[i][j] == ch) {
for(int p = 0; p < 4; p++) {
int l = i + dl[p], c = j + dc[p];
if(in(l, c)) {
myunion(get(l, c), get(i, j));
}
}
}
}
}
memset(vis, 0, sizeof(vis));
int ans = 1;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(mat[i][j] == ch) {
if(!vis[myfind(get(i, j))]) {
vis[myfind(get(i, j))] = 1;
ans++;
}
}
}
}
return ans;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, j;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int cntF = 0, cntR = 0;
for(i = 1; i <= n; i++) {
cin >> mat[i] + 1;
for(j = 1; j <= m; j++) {
if(mat[i][j] == 'R') {
cntR++;
}
if(mat[i][j] == 'F') {
cntF++;
}
}
}
if(cntF + cntR == 0) {
cout << 0;
return 0;
}
if(cntF == 0 || cntR == 0) {
cout << 1;
return 0;
}
int ans = solve('R');
ans = min(ans, solve('F'));
cout << ans;
//cin.close();
//cout.close();
return 0;
}
Compilation message (stderr)
tracks.cpp: In function 'int main()':
tracks.cpp:79:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
cin >> mat[i] + 1;
~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |