QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106252#4231. Rafting Tripzaxwellmen#RE 2ms3324kbC++202.9kb2023-05-17 02:35:352023-05-17 02:35:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 02:35:39]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3324kb
  • [2023-05-17 02:35:35]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define mp make_pair

// right down left up
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
map<char, int> dir = {{'>', 0}, {'v', 1}, {'<', 2}, {'^', 3}};
int n, m, ans;
vector<string> grid;
vector<vector<bool>> vis, iscycle;
vector<vector<pi>> tail;
map<pi, int> cnt;

bool river(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m && dir.find(grid[i][j]) != dir.end();
}
bool landmark(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m && grid[i][j]=='#';
}
void check(int i, int j) {
    if (tail[i][j] != mp(-1, -1)) return;
    if (vis[i][j]) {
        tail[i][j] = mp(i, j);
        iscycle[i][j] = true;
        int x = i, y = j;
        do {
            int d = dir[grid[x][y]];
            x += dx[d], y += dy[d];
            iscycle[x][y] = true;
        } while (mp(x,y) != mp(i,j));
        return;
    }
    vis[i][j] = true;
    int d = dir[grid[i][j]], ni = i+dx[d], nj = j+dy[d];
    if (! river(ni, nj)) {
        tail[i][j] = mp(i,j);
        vis[i][j] = false;
        return;
    }
    check(ni, nj);
    tail[i][j] = tail[ni][nj];
    vis[i][j] = false;
    return;
}
void dfs(int i, int j) {
    if (vis[i][j]) return;
    vis[i][j] = true;
    F0R(d, 4) if (landmark(i+dx[d], j+dy[d])) cnt[mp(i+dx[d], j+dy[d])]++;
    ans = max(ans, (int)cnt.size());
    F0R(d, 4) {
        int ni = i+dx[d], nj = j+dy[d];
        if (river(ni, nj) && dir[grid[ni][nj]] == (d+2)%4) dfs(ni, nj);
    }
    F0R(d, 4) if (landmark(i+dx[d], j+dy[d])) {
        pi p = mp(i+dx[d], j+dy[d]);
        if (cnt[p]==1) cnt.erase(p);
        else cnt[p]--;
    }
    vis[i][j] = false;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    grid.resize(n);
    F0R(i, n) cin >> grid[i];
    vis.assign(n, vector<bool>(m, false));
    iscycle = vis;
    tail.assign(n, vector<pi>(m, mp(-1, -1)));
    F0R(i, n) F0R(j, m) {
        if (river(i,j)) {
            int d = dir[grid[i][j]];
            if (! river(i + dx[d], j + dy[d])) {
                dfs(i, j);
            } else check(i, j);
        }
    }
    F0R(i, n) F0R(j, m) if (iscycle[i][j]) {
        int x = i, y = j;
        vector<pi> starts;
        do {
            iscycle[x][y] = false;
            F0R(d, 4) {
                int nx = x+dx[d], ny = y+dy[d];
                if (landmark(nx, ny)) cnt[mp(nx, ny)]++;
                if (river(nx, ny) && dir[grid[nx][ny]] == (d+2)%4) starts.push_back(mp(nx, ny));
            }
            int d = grid[x][y];
            x += dx[d]; y += dy[d];
        } while (mp(x,y) != mp(i,j));
        ans = max(ans, (int)cnt.size());
        for (pi p : starts) dfs(p.first, p.second);
        cnt.clear();
    }
    cout << ans << '\n';
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3324kb

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

score: -100
Runtime Error

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:


result: