QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471740#5485. MazeManKerollos#WA 0ms3852kbC++172.3kb2024-07-11 06:10:242024-07-11 06:10:25

Judging History

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

  • [2024-07-11 06:10:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2024-07-11 06:10:24]
  • 提交

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;
                break;
            }
        }
    }
    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: 3528kb

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: 3792kb

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: 3852kb

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: 3620kb

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
Wrong Answer
time: 0ms
memory: 3664kb

input:

7 4
WIRX
VX.S
OXXN
XX E
K..B
T.XQ
CMDL

output:

5 -9

result:

wrong answer 1st numbers differ - expected: '2', found: '5'