QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #846140 | #3172. Tomb Raider | AlicX | WA | 4ms | 14044kb | C++20 | 5.2kb | 2025-01-06 22:27:01 | 2025-01-06 22:27:02 |
Judging History
answer
#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long
#define pos(x,y) ((x - 1) * m + y)
using namespace std;
typedef pair<int,int> pii;
const int N = 510,M = 2 * N * N;
const int inf = 1e9 + 10;
int n,m,ans;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
bool falg;
int val[M],col[M];
pii id[M];
char arr[N][N];
vector<int> v[2],g[M];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int dfs(int x,int y,int w){
// 0：右 1：左 2：上 3：下
// cerr << x << " " << y << " " << w << " ???\n";
if (falg){
if (arr[x][y] == '#') return -1;
else if (arr[x][y] == 'H'){
if (w <= 1) return pos(x,y) + n * m;
else return pos(x,y);
}
else if (arr[x][y] == 'V'){
if (w <= 1) return pos(x,y);
else return pos(x,y) + n * m;
}
} falg = true;
if (arr[x][y] == '/') w ^= 2;
if (arr[x][y] == '\\') w ^= 3;
if (!x || x == n + 1 || !y || y == m + 1) w ^= 1;
// cerr << x << " " << y << " " << w << " !!!\n";
return dfs(x + dx[w],y + dy[w],w);
}
inline void dfs(int u,bool w){
v[col[u] = w].push_back(u);
// cerr << id[u].fst << " " << id[u].snd << " " << w << " !!!\n";
for (int v:g[u]){
if (!~col[v]) dfs(v,w ^ 1);
else if (col[v] != (w ^ 1)&&(u!=v)){
// cerr << u << " " << v << " " << id[u].fst << " " << id[u].snd << " " << id[v].fst << " " << id[v].snd << " sbsb\n";
puts("-1"); exit(0);
}
}
}
signed main(){
n = read(),m = read();
for (re int i = 1;i <= n;i++) scanf("%s",arr[i] + 1);
for (re int i = 1;i <= n;i++){
for (re int j = 1;j <= m;j++) id[pos(i,j)] = id[pos(i,j) + n * m] = {i,j};
}
// cerr << dfs(1,2,1); return 0;
for (re int i = 1;i <= n;i++){
for (re int j = 1;j <= m;j++){
if (arr[i][j] == 'H' || arr[i][j] == 'V'){
val[pos(i,j) + n * m] = 1;
g[pos(i,j)].push_back(pos(i,j) + n * m);
g[pos(i,j) + n * m].push_back(pos(i,j));
}
}
}
for (re int i = 1;i <= n;i++){
for (re int j = 1;j <= m;j++){
if (arr[i][j] == 'H'){
falg = false; int li = dfs(i,j,1);
falg = false; int ri = dfs(i,j,0);
if (!~li || !~ri) val[pos(i,j)] = inf;
else{
g[pos(i,j)].push_back(li);
g[pos(i,j)].push_back(ri);
// cerr << li << " " << ri << " !!!\n";
// fprintf(stderr,"(%d,%d) -> (%d,%d),(%d,%d) 1\n",i,j,id[li].fst,id[li].snd,id[ri].fst,id[ri].snd);
}
falg = false; li = dfs(i,j,2);
falg = false; ri = dfs(i,j,3);
if (!~li || !~ri) val[pos(i,j) + n * m] = inf;
else{
g[pos(i,j) + n * m].push_back(li);
g[pos(i,j) + n * m].push_back(ri);
// cerr << li << " " << ri << " !!!\n";
// fprintf(stderr,"(%d,%d) -> (%d,%d),(%d,%d) 2\n",i,j,id[li].fst,id[li].snd,id[ri].fst,id[ri].snd);
}
}
else if (arr[i][j] == 'V'){
// cerr << dfs(2,4,3,false) << " sbsb\n";
falg = false; int li = dfs(i,j,2);
falg = false; int ri = dfs(i,j,3);
if (!~li || !~ri) val[pos(i,j)] = inf;
else{
g[pos(i,j)].push_back(li);
g[pos(i,j)].push_back(ri);
// cerr << li << " " << ri << " ???\n";
// fprintf(stderr,"(%d,%d) -> (%d,%d),(%d,%d) 1\n",i,j,id[li].fst,id[li].snd,id[ri].fst,id[ri].snd);
}
falg = false; li = dfs(i,j,0);
falg = false; ri = dfs(i,j,1);
if (!~li || !~ri) val[pos(i,j) + n * m] = inf;
else{
g[pos(i,j) + n * m].push_back(li);
g[pos(i,j) + n * m].push_back(ri);
// cerr << li << " " << ri << " ???\n";
// fprintf(stderr,"(%d,%d) -> (%d,%d),(%d,%d) 2\n",i,j,id[li].fst,id[li].snd,id[ri].fst,id[ri].snd);
}
}
}
}
memset(col,-1,sizeof(col));
for (re int i = 1;i <= n;i++){
for (re int j = 1;j <= m;j++){
if (arr[i][j] == 'H' || arr[i][j] == 'V'){
if (~col[pos(i,j)]) continue;
v[0].clear(),v[1].clear();
dfs(pos(i,j),false);
int suma = 0,sumb = 0;
for (int x:v[0]) suma += val[x];
for (int x:v[1]) sumb += val[x];
ans += min(suma,sumb);
}
}
}
// cerr << ans << " ans\n";
if (ans < inf) printf("%lld",ans);
else puts("-1");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12148kb
input:
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11872kb
input:
2 5 V...\ H...V
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 11988kb
input:
2 2 VV VV
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 12016kb
input:
4 3 /.\ H.. \H. ..H
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 4ms
memory: 12068kb
input:
5 5 ..... .H.V. ..... .H.H. .....
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 11812kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \........./.
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 14044kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \\......../.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 4ms
memory: 11808kb
input:
2 2 #H V#
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 12068kb
input:
2 2 V. \#
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 4ms
memory: 13912kb
input:
2 2 V# \#
output:
-1
result:
ok single line: '-1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 11960kb
input:
3 5 V.#.\ ./\.. \/\./
output:
-1
result:
ok single line: '-1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 11960kb
input:
2 2 /# H/
output:
-1
result:
ok single line: '-1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 12084kb
input:
1 1 H
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 11960kb
input:
2 1 V #
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 3ms
memory: 12080kb
input:
1 2 #H
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 3ms
memory: 11960kb
input:
5 5 V\#VH H/#\/ ##### /\#/V VH#\H
output:
4
result:
ok single line: '4'
Test #17:
score: 0
Accepted
time: 0ms
memory: 12084kb
input:
4 5 /.\/# .///\ .\V/. \.../
output:
1
result:
ok single line: '1'
Test #18:
score: -100
Wrong Answer
time: 3ms
memory: 12068kb
input:
3 3 /\# \.\ #\H
output:
0
result:
wrong answer 1st lines differ - expected: '-1', found: '0'