QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471735#5485. MazeManKerollos#RE 0ms3848kbC++172.3kb2024-07-11 06:04:572024-07-11 06:04:57

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 06:04:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3848kb
  • [2024-07-11 06:04:57]
  • 提交

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

output:


result: