QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #409449 | #3172. Tomb Raider | Massachusetts Institute of Terriers (Yi Du, Mutiraj Laksanawisit)# | WA | 0ms | 3880kb | C++20 | 8.8kb | 2024-05-12 06:28:05 | 2024-05-12 06:28:06 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> S(n);
for(int i=0; i<n; i++) cin >> S[i];
vector<vector<pair<int, int>>> adj(n*m);
vector<bool> canV(n*m, true), canH(n*m, true);
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(S[i][j] == 'V' || S[i][j] == 'H')
{
//0 -> U, 1 -> R, 2 -> D, 3 -> L
for(int d = 0; d < 4; d++)
{
int curi = i, curj = j, dir = d;
bool cont = true;
while(cont)
{
switch(dir)
{
case 0:
if(curi - 1 >= 0)
{
curi--;
if(S[curi][curj] == '#')
{
if(d%2==0) canV[i*m+j] = false;
else canH[i*m+j] = false;
cont = false;
}
else if(S[curi][curj] == '/') dir = 1;
else if(S[curi][curj] == '\\') dir = 3;
else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
}
else
{
if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
dir = 2;
}
break;
case 1:
if(curj + 1 < m)
{
curj++;
if(S[curi][curj] == '#')
{
if(d%2==0) canV[i*m+j] = false;
else canH[i*m+j] = false;
cont = false;
}
else if(S[curi][curj] == '/') dir = 0;
else if(S[curi][curj] == '\\') dir = 2;
else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
}
else
{
if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
dir = 3;
}
break;
case 2:
if(curi + 1 < n)
{
curi++;
if(S[curi][curj] == '#')
{
if(d%2==0) canV[i*m+j] = false;
else canH[i*m+j] = false;
cont = false;
}
else if(S[curi][curj] == '/') dir = 3;
else if(S[curi][curj] == '\\') dir = 1;
else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
}
else
{
if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
dir = 0;
}
break;
case 3:
if(curj - 1 >= 0)
{
curj--;
if(S[curi][curj] == '#')
{
if(d%2==0) canV[i*m+j] = false;
else canH[i*m+j] = false;
cont = false;
}
else if(S[curi][curj] == '/') dir = 2;
else if(S[curi][curj] == '\\') dir = 0;
else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
}
else
{
if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
{
adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
cont = false;
}
dir = 1;
}
break;
}
}
}
}
}
}
/*for(vector<pair<int, int>> vp: adj)
{
for(pair<int, int> p: vp)
{
cout << "(" << p.first << ", " << p.second << ") ";
}
cout << "\n";
}*/
bool valid = true;
int ans = 0;
vector<int> c(n*m, -1);
for(int i=0; i<n*m; i++)
{
if(c[i]==-1 && (S[i/m][i%m] == 'V' || S[i/m][i%m] == 'H'))
{
c[i] = 0;
vector<int> cc;
queue<int> Q;
Q.push(i);
while(valid && !Q.empty())
{
int p = Q.front();
cc.pb(p);
Q.pop();
for(pair<int, int> x: adj[p])
{
int v = x.first, d = x.second;
if(c[v]==-1)
{
c[v] = (c[p] + d) % 2;
Q.push(v);
}
else if(c[v] != (c[p] + d) % 2)
{
valid = false;
}
}
}
if(!valid) break;
bool H = true, V = true;
int cH = 0, cV = 0;
for(int x: cc)
{
if(c[x] == 0)
{
if(canH[x]) cH += S[x/m][x%m] == 'V';
else H = false;
if(canV[x]) cV += S[x/m][x%m] == 'H';
else V = false;
}
else
{
if(canV[x]) cH += S[x/m][x%m] == 'H';
else H = false;
if(canH[x]) cV += S[x/m][x%m] == 'V';
else V = false;
}
}
//cout << i << " : " << H << " -> " << cH << " " << V << " -> " << cV << "\n";
if(!H && !V) valid = false;
else if(H && V) ans += min(cH, cV);
else if(H) ans += cH;
else ans += cV;
}
}
if(valid) cout << ans;
else cout << -1;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
input:
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
2 5 V...\ H...V
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 VV VV
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 3 /.\ H.. \H. ..H
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
5 5 ..... .H.V. ..... .H.H. .....
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \........./.
output:
-1
result:
ok single line: '-1'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3844kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \\......../.
output:
-1
result:
wrong answer 1st lines differ - expected: '3', found: '-1'