#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
using namespace std;
const long long oo = 1000000000000000000;
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen ( "sum.in", "r", stdin )
*/
char c[ 501 ][ 501 ];
int k, n, m, d[ 10 ][ 250001 ], pr[ 10 ], p[ 10 ], r[ 10 ];
set <pair<int, int> > st;
vector <int> v[ 250001 ];
vector <pair<int, pair<int, int> > > vv;
void f( int i, int j ) {
if ( !i || !j || i > n || j > m )
return;
pos = ( i - 1 ) * m + j;
if ( ans == 1 ) {
i --;
if ( c[ i ][ j ] == 'x' )
return;
if ( c[ i ][ j ] == 'A' )
ans = 4;
if ( c[ i ][ j ] == 'C' )
ans = 2;
return f( i, j );
}
else if ( ans == 2 ) {
j ++;
if ( c[ i ][ j ] == 'x' )
return;
if ( c[ i ][ j ] == 'A' )
ans = 1;
if ( c[ i ][ j ] == 'C' )
ans = 3;
return f( i, j );
}
else if ( ans == 3 ) {
i ++;
if ( c[ i ][ j ] == 'x' )
return;
if ( c[ i ][ j ] == 'A' )
ans = 2;
else if ( c[ i ][ j ] == 'C' )
ans = 4;
return f( i, j );
}
else {
j --;
if ( c[ i ][ j ] == 'x' )
return;
if ( c[ i ][ j ] == 'A' )
ans --;
else if ( c[ i ][ j ] == 'C' )
ans = 1;
return f( i, j );
}
}
int fin( int a ) {
if ( pr[ a ] == a )
return a;
return pr[ a ] = fin( pr[ a ] );
}
void unin( int a, int b ) {
a = fin( a );
b = fin( b );
if ( a == b )
return;
if ( r[ a ] < r[ b ] )
swap( a, b );
r[ a ] += r[ b ];
pr[ b ] = a;
}
main () {
cin >> k >> m >> n;
for ( int i = 1; i <= k; i ++ )
pr[ i ] = i, r[ i ] = 1;
for ( int i = 1; i <= n; i ++ ) {
for ( int j = 1; j <= m; j ++ ) {
cin >> c[ i ][ j ];
num = ( i - 1 ) * m + j;
if ( c[ i ][ j ] >= '1' && c[ i ][ j ] <= '9' )
p[ c[ i ][ j ] - '0' ] = num;
}
}
for ( int i = 1; i <= n; i ++ ) {
for ( int j = 1; j <= m; j ++ ) {
num = ( i - 1 ) * m + j;
pos = num;
ans = 1;
f( i, j );
v[ num ].push_back( pos );
pos = num;
ans = 2;
f( i, j );
v[ num ].push_back( pos );
pos = num;
ans = 3;
f( i, j );
v[ num ].push_back( pos );
pos = num;
ans = 4;
f( i, j );
v[ num ].push_back( pos );
}
}
for ( int i = 1; i <= k; i ++ ) {
for ( int j = 1; j <= n * m; j ++ )
d[ i ][ j ] = oo;
d[ i ][ p[ i ] ] = 0;
st.insert( { d[ i ][ p[ i ] ], p[ i ] } );
while ( st.size() ) {
num = st.begin()->second;
st.erase( st.begin() );
for ( auto to : v[ num ] ) {
if ( d[ i ][ to ] > d[ i ][ num ] + 1 ) {
st.erase( { d[ i ][ to ], to } );
d[ i ][ to ] = d[ i ][ num ] + 1;
st.insert( { d[ i ][ to ], to } );
}
}
}
}
// for ( int i = 1; i <= k; i ++ ) {
// for ( int j = 1; j <= k; j ++ ) {
// vv.push_back( { d[ i ][ p[ j ] ], make_pair( i, j ) } );
// }
// }
// sort( vv.begin(), vv.end() );
// ans = 0;
// for ( auto i : vv ) {
// if ( fin( i.second.first ) != fin( i.second.second ) ) {
// cout << i.second.first << " " << i.second.second << "\n";
// ans += i.first;
// unin( i.second.second, i.second.first );
// }
// }
if ( k == 2 ) {
for ( int i = 1; i <= n * m; i ++ ) {
ans = min( ans, d[ 1 ][ i ] + d[ 2 ][ i ] );
}
}
cout << ans;
}
Compilation message
robots.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
115 | main () {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6092 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
