| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
过了Discuss区能找到的所有数据,但是一直WA,崩溃。。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator