Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

过了Discuss区能找到的所有数据,但是一直WA,崩溃。。。

Posted by C5Compound at 2019-08-18 00:05:32 on Problem 3083
#include <cstdio>
#include <queue>
using namespace std;

int direct[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
char M[50][50];
int W;
int H;

// -1 for clockwise 1 for counterclockwise
int clockround(int i, int j, int r, int flag) {
    if (M[i][j] == 'E') {
        return 0;
    }
    int re = -1;
    for (int p = 0; p < 4; ++p) {
        int tr = (r + flag + 4 - flag * p) % 4;
        int ti = i - flag * direct[tr][0], tj = j - flag * direct[tr][1];
        if (ti < 0 || ti >= H || tj < 0 || tj >= W || M[ti][tj] == '#') {
            continue;
        }
        re = 1 + clockround(ti, tj, tr, flag);
        break;
    }
    return re;
}

int shortest(int i, int j) {
    queue<int> Q;
    Q.push(i * W + j);
    M[i][j] = '#';
    int re = 0;
    while (!Q.empty()) {
        int s = Q.size();
        while (s--) {
            int ps = Q.front(), i = ps / W, j = ps % W;
            Q.pop();
            for (int p = 0; p < 4; ++p) {
                int ti = i + direct[p][0], tj = j + direct[p][1];
                if (ti < 0 || ti >= H || tj < 0 || tj >= W || M[ti][tj] == '#') {
                    continue;
                } 
                if (M[ti][tj] == 'E') {
                    return 1 + re;
                }
                M[ti][tj] = '#';
                Q.push(ti * W + tj);
            }
        }
        ++re;
    }
    return -1;
}

int main(int argc, char **argv) {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%*c", &W, &H);
        int si, sj;
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                M[i][j] = getchar();
                if (M[i][j] == 'S') {
                    si = i, sj = j;
                }
            }
            getchar();
        }
        printf("%d %d %d\n", 1 + clockround(si, sj, 0, -1), 1 + clockround(si, sj, 0, 1), 1 + shortest(si, sj));
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator