QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611272 | #7034. Honeycomb | ucup-team4906# | WA | 3ms | 9776kb | C++20 | 3.0kb | 2024-10-04 20:09:03 | 2024-10-04 20:09:18 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define pii pair<int, int>
using namespace std;
const int inf = 1e9;
int n, m, idx = 0;
char a[4010][6010];
int id[1005][1005];
const int N = 1e6 + 10;
vector<int> ed[N];
int dis[N], vst[N];
int s, t;
void init(vector<vector<char>> x, int now, int i, int j) {
if(x[2][4] == 'S') s = now;
if(x[2][4] == 'T') t = now;
if(x[0][3] != '-') { // 上面
ed[now].push_back(id[i - 1][j]);
}
if(x[4][3] != '-') {
ed[now].push_back(id[i + 1][j]);
}
if(x[1][1] != '/') {
if(j % 2) ed[now].push_back(id[i - 1][j - 1]);
else ed[now].push_back(id[i][j - 1]);
}
if(x[3][1] != '\\') {
if(j % 2) ed[now].push_back(id[i][j - 1]);
else ed[now].push_back(id[i + 1][j - 1]);
}
if(x[1][7] != '\\') {
if(j % 2) ed[now].push_back(id[i - 1][j + 1]);
else ed[now].push_back(id[i][j + 1]);
}
if(x[3][7] != '/') {
if(j % 2) ed[now].push_back(id[i][j + 1]);
else ed[now].push_back(id[i + 1][j + 1]);
}
}
void sol() {
cin >> n >> m;
getchar();
F(i, 0, 4 * n + 2) {
string s;
getline(cin, s);
int now = 0;
for(auto x : s) a[i][now ++] = x;
for(int j = s.size(); j < 6 * m + 3; j ++) a[i][j] = ' ';
}
idx = 0;
F(i, 1, n) F(j, 1, m) id[i][j] = ++ idx;
F(i, 1, idx) ed[i].clear();
F(i, 1, n) F(j, 1, m) {
vector<vector<char>> now(5);
int cnt = 0;
if(j % 2) {
F(c, 4 * (i - 1), 4 * i) {
F(r, 6 * (j - 1), 6 * (j - 1) + 8)
now[cnt].push_back(a[c][r]);
cnt ++;
}
} else {
F(c, 4 * (i - 1) + 2, 4 * i + 2) {
F(r, 6 * (j - 1), 6 * (j - 1) + 8)
now[cnt].push_back(a[c][r]);
cnt ++;
}
}
init(now, id[i][j], i, j);
}
F(i, 1, idx) dis[i] = inf, vst[i] = 0;
dis[s] = 0;
queue<int> q;
q.push(s);
while(q.size()) {
auto u = q.front();
q.pop();
if(vst[u]) continue;
vst[u] = 1;
for(auto v : ed[u]) {
if(dis[u] + 1 < dis[v]) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
if(dis[t] == inf) cout << "-1\n";
else cout << dis[t] + 1 << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
F(i, 1, t) sol();
return 0;
}
/*
1
3 4
+---+ +---+
/ \ / \
+ +---+ +---+
\ \ / \
+ + S +---+ T +
/ \ / /
+ +---+ + +
\ \ / \
+---+ +---+ +
/ /
+ +---+ + +
\ / \
+---+ +---+ +
\ / \ /
+---+ +---+
*/
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 9776kb
input:
1 3 4 +---+ +---+ / \ / \ + +---+ +---+ \ \ / \ + + S +---+ T + / \ / / + +---+ + + \ \ / \ +---+ +---+ + / / + +---+ + + \ ...
output:
1
result:
wrong answer 1st lines differ - expected: '7', found: '1'