| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1001874 |
2024-06-19T08:12:57 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
3 ms |
7004 KB |
/*
Dimash ne katai!!!
shnurok krash))
Serikbay777 tozhe krash))
*/
#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define Respaabs1equal2xdoner ios_base::sync_with_stdio(0);cin.tie(0);
#define pll pair < long long , long long >
#define all(x) x.begin() , x.end()
#define pii pair < int , int >
#define pofik continue
#define int long long
#define pb push_back
#define ins insert
#define sz size()
#define F first
#define S second
const long long N = 300 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-11;
using namespace std;
int T = 1;
int binpow(int a , int b){
if(!b) return 1;
int val = binpow(a , b / 2);
if(b % 2 == 0) return val * val % MOD;
else return val * val * a % MOD;
}
/*
1.........
AA.x4.....
..A..x....
2....x....
..C.3.A...
*/
set < pll > g[N][N];
int dst[N][N];
bool is_digit(char c){
if('0' <= c && c <= '9') return 1;
return 0;
}
void solve(){
int n , h , w;
cin >> n >> h >> w;
swap(h , w);
char c[h + 1][w + 1];
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> c[i][j];
dst[i][j] = inf;
}
}
queue < pll > t;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(c[i][j] == 'x') pofik;
map < pair < pll , int > , int > mp;
int cur , x , y;
bool ok;
cur = 1;
x = i , y = j;
ok = 1;
while(ok){
if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
if(mp[{{x , y} , cur}]) break;
mp[{{x , y} , cur}] = 1;
if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
if(c[x][y] == 'C') cur = (cur + 1) % 4;
if(cur == 0){
if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
x--;
}
if(cur == 1){
if(y == w || (y < w && c[x][y + 1] == 'x')) break;
y++;
}
if(cur == 2){
if(x == h || (x < h && c[x + 1][y] == 'x')) break;
x++;
}
if(cur == 3){
if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
y--;
}
}
if(x != h + 1){
g[x][y].ins({i , j});
}
mp.clear();
cur = 2;
x = i , y = j;
ok = 1;
while(ok){
if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
if(mp[{{x , y} , cur}]) break;
mp[{{x , y} , cur}] = 1;
if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
if(c[x][y] == 'C') cur = (cur + 1) % 4;
if(cur == 0){
if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
x--;
}
if(cur == 1){
if(y == w || (y < w && c[x][y + 1] == 'x')) break;
y++;
}
if(cur == 2){
if(x == h || (x < h && c[x + 1][y] == 'x')) break;
x++;
}
if(cur == 3){
if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
y--;
}
}
if(x != h + 1){
g[x][y].ins({i , j});
}
mp.clear();
cur = 3;
x = i , y = j;
ok = 1;
while(ok){
if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
if(mp[{{x , y} , cur}]) break;
mp[{{x , y} , cur}] = 1;
if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
if(c[x][y] == 'C') cur = (cur + 1) % 4;
if(cur == 0){
if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
x--;
}
if(cur == 1){
if(y == w || (y < w && c[x][y + 1] == 'x')) break;
y++;
}
if(cur == 2){
if(x == h || (x < h && c[x + 1][y] == 'x')) break;
x++;
}
if(cur == 3){
if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
y--;
}
}
if(x != h + 1){
g[x][y].ins({i , j});
}
mp.clear();
cur = 0;
x = i , y = j;
ok = 1;
while(ok){
if(mp[{{x , y} , cur}]) x = h + 1 , y = w + 1;
if(mp[{{x , y} , cur}]) break;
mp[{{x , y} , cur}] = 1;
if(c[x][y] == 'A') cur = (cur - 1 + 4) % 4;
if(c[x][y] == 'C') cur = (cur + 1) % 4;
if(cur == 0){
if(x == 1 || (x > 1 && c[x - 1][y] == 'x')) break;
x--;
}
if(cur == 1){
if(y == w || (y < w && c[x][y + 1] == 'x')) break;
y++;
}
if(cur == 2){
if(x == h || (x < h && c[x + 1][y] == 'x')) break;
x++;
}
if(cur == 3){
if(y == 1 || (y > 1 && c[x][y - 1] == 'x')) break;
y--;
}
}
if(x != h + 1){
g[x][y].ins({i , j});
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(is_digit(c[i][j])){
for(pll to : g[i][j]){
t.push(to);
}
}
}
}
int ans = inf;
while(t.sz){
pll x = t.front();
t.pop();
dst[x.F][x.S] = 0;
queue < pll > q;
q.push(x);
while(q.sz){
pll v = q.front();
q.pop();
for(pll to : g[v.F][v.S]){
if(dst[to.F][to.S] > dst[v.F][v.S] + 1){
dst[to.F][to.S] = dst[v.F][v.S] + 1;
q.push(to);
}
}
}
int sum = 0;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(is_digit(c[i][j])) sum += dst[i][j];
// if(x.F == 1 && x.S == 1){
// cout << dst[i][j] << ' ';
// }
dst[i][j] = inf;
}
// cout << '\n';
}
ans = min(ans , sum);
// cout << x.F << ' ' << x.S << ' ' << sum << '\n';
}
cout << ans << '\n';
// for(int i = 1; i <= h; i++){
// for(int j = 1; j <= w; j++){
// cout << i << ' ' << j << ":\n";
// for(pll to : g[i][j]){
// cout << to.F << ' ' << to.S << '\n';
// }
// cout << '\n';
// }
// }
}
signed main(){
Respaabs1equal2xdoner
// cin >> T;
for(int cas = 1; cas <= T; cas++){
// cout << "Case " << cas << ":\n";
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
