/* author : Dinmukhammed ^_^ */
#include <map>
#include <set>
#include <unordered_set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#include <complex>
#define ll long long
#define ld long double
#define all(x) (x).begin() , (x).end()
#define F first
#define S second
#define sz size()
#define turbo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ins insert
#define rall(x) (x).rbegin() , (x).rend()
#define int ll
// #ifdef cp_editor
// #else
// freopen(".in" , "r" , stdin);
// freopen(".out" , "w" , stdout);
// #endif
// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
using namespace std;
const ll inf = 1e18+3;
const int MOD = 1e9+7;
const long double eps = 1e-11;
ll rnd(){
ll x = rand() << 15;
return rand() ^ x;
}
ll binpow(ll a , ll b){
if (!b) return 1;
if (b % 2){
return (a * binpow(a , b - 1)) % MOD;
}
else{
ll val = binpow(a , b / 2);
return (val * val) % MOD;
}
}
const int N = 500 + 3;
const int NN = 2e6+3;
const int N1 = 2000+3;
const int lg = 22;
const int dx[] = {1 , 0 , -1 , 0};
const int dy[] = {0 , 1 , 0 , -1};
int n , m , coln;
char a[N][N];
int id = 0;
pair <int , int> used[N][N][4];
pair <int , int> find(int x , int y , int k){
if(used[x][y][k].F) return used[x][y][k];
used[x][y][k] = {-1 , -1};
int k1 = k;
if(a[x][y] == 'C') k = (k - 1 + 4) % 4;
if(a[x][y] == 'A') k = (k + 1) % 4;
if(a[x + dx[k]][y + dy[k]] == 'x' || (x + dx[k] < 1 || y + dy[k] < 1 || x + dx[k] > n || y + dy[k] > m)) return used[x][y][k1] = {x , y};
return used[x][y][k1] = find(x + dx[k] , y + dy[k] , k);
}
vector <pair <int , int>> g[N][N];
void build(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == 'x') continue;
for(int k = 0; k < 4; k++){
pair <int , int> p = find(i , j , k);
if(p.F != -1) g[i][j].pb(p);
}
}
}
}
void code(){
cin >> coln >> m >> n;
vector <pair <int , pair <int , int>>> rbt;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j] >= '1' && a[i][j] <= '9') rbt.pb({a[i][j] - '0' , {i , j}});
}
}
build();
ll dp[coln + 1][coln + 1][n + 1][m + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
for(int l = 1; l <= coln; l++){
for(int r = l; r <= coln; r++) dp[l][r][i][j] = inf;
}
}
}
for(auto [ind , cor] : rbt){
dp[ind][ind][cor.F][cor.S] = 0;
}
for(int sz1 = 1; sz1 <= coln; sz1++){
for(int l = 1; l <= coln - sz1 + 1; l++){
int r = l + sz1 - 1;
set <pair <int , pair <int , int>>> st;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
for(int mid = l; mid < r; mid++){
dp[l][r][i][j] = min(dp[l][r][i][j] , dp[l][mid][i][j] + dp[mid + 1][r][i][j]);
}
if(dp[l][r][i][j] != inf) st.ins({dp[l][r][i][j] , {i , j}});
}
}
while(!st.empty()){
int x , y;
tie(x , y) = st.begin() -> S;
st.erase(st.begin());
for(auto to : g[x][y]){
if(dp[l][r][to.F][to.S] > dp[l][r][x][y] + 1){
st.erase({dp[l][r][to.F][to.S] , to});
dp[l][r][to.F][to.S] = dp[l][r][x][y] + 1;
st.ins({dp[l][r][to.F][to.S] , to});
}
}
}
}
}
ll mn = inf;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
mn = min(mn , dp[1][coln][i][j]);
}
}
// for(auto to : g[5][5]){
// cout << to.F << " " << to.S << "\n";
// }
// cout << dp[3][4][1][7] << " ";
if(mn == inf) cout << -1;
cout << mn;
}
signed main(/* oblys -> respa -> mezhdynarodka */){
turbo
// freopen("haircut.in" , "r" , stdin);
// freopen("haircut.out" , "w" , stdout);
int tt = 1;
// cin >> tt;
for(int _ = 1; _ <= tt; _++){
code();
// cout << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
