QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471735 | #5485. MazeMan | Kerollos# | RE | 0ms | 3848kb | C++17 | 2.3kb | 2024-07-11 06:04:57 | 2024-07-11 06:04:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 105;
int reach[N][N][26];
bool vis[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> grid(n);
cin.ignore();
for (int i = 0; i < n; i++){
getline(cin, grid[i]);
}
vector<int> ans(26);
auto check = [&](int i, int j){
return i >= 0 && i < n && j >= 0 && j < m && (grid[i][j] == '.' || grid[i][j] == ' ');
};
auto BFS = [&](int sti, int stj){
char c = grid[sti][stj] - 'A';
queue<pair<int, int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) vis[i][j] = 0;
q.push({sti, stj});
while (q.size()){
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; d++){
int nxtX = x + dx[d], nxtY = y + dy[d];
if (check(nxtX, nxtY) && !vis[nxtX][nxtY]){
q.push({nxtX, nxtY});
vis[nxtX][nxtY] = 1;
if (grid[nxtX][nxtY] == '.'){
ans[c]++, reach[nxtX][nxtY][c] = 1;
}
}
}
}
};
int tot = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (grid[i][j] >= 'A' && grid[i][j] <= 'W') {
BFS(i, j);
}
else if (grid[i][j] == '.') tot++;
}
}
for (char a = 0; a < 23; a++){
for (char b = 0; b < a; b++){
bool same = 1;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (reach[i][j][a] != reach[i][j][b]){
same = 0;
break;
}
}
if (!same) break;
}
if (same){
assert(ans[a] == ans[b]);
ans[b] = 0;
}
}
}
int can = 0, cnt = 0;
for (int i = 0; i < 23; i++){
if (ans[i]) can += ans[i], cnt++;
}
cout << cnt << ' ' << tot - can;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
10 20 XXXXXXXAXXXXXXXBXXXX X.. ..X.X...... ...X X.XXX...X.X.XXXXXX.X X.X.XXXXX.X.X....X.X X.X... ...X.X.XX.X.X X.X.X.XXXXXXX.XX.X.X X.X.X.X...X...X....X X.X.X.XXXXXXX.XXXX.X X...X.X X.. ..X..X.X XXXXXXXDXXXXXXXXCXXX
output:
2 3
result:
ok 2 number(s): "2 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 5 XDRVX X.X.X XXXXX
output:
2 0
result:
ok 2 number(s): "2 0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 5 NAQXX X X.X XXXXX
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
10 68 XXXXXXPXXXXXXXXCXXXXXXXXXXXXXXXXXXXXHXXXXXXXXXXXXXXIXXRXXXXXXXXXKXXX X.XX..XXXX.X.X.XXXXXX..XXXXX.X.X......X ......X.X.. X.....XXX.. X.X X X.X.XXX.. X..X..X ..X..XX.XX.XXXXX.X....X.X.X.XXXX.X. X..X.X.....X X.X..XX .XX..X....X.XX.X..XXX....X.X. .X....X.X .XX.X...X.XXX.. X..X X.X..X..XXXXXX .. ...
output:
4 116
result:
ok 2 number(s): "4 116"
Test #5:
score: -100
Runtime Error
input:
7 4 WIRX VX.S OXXN XX E K..B T.XQ CMDL