#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
const int K = 10;
const int DIM = 500 + 7;
const int INF = (int)1e9 + 7;
const int dr[] = { -1, 0, 1, 0 };
const int dc[] = { 0, 1, 0, -1 };
int dp[DIM][DIM][K][K];
int k;
int cntrows;
int cntcols;
int a[DIM][DIM];
int adddir[DIM][DIM];
pair<int, int> w[DIM][DIM][4];
bool isvalid(int i, int j)
{
return 1 <= i && i <= cntrows && 1 <= j && j <= cntcols;
}
pair<int, int> go(int r, int c, int k)
{
int rn = r + dr[k];
int cn = c + dc[k];
if (!isvalid(rn, cn))
{
return { r, c };
}
if (a[rn][cn] == -1)
{
return { r, c };
}
r = rn;
c = cn;
k = (k + adddir[r][c]) % 4;
return go(r, c, k);
}
struct T
{
int i;
int j;
int st;
int dr;
};
bool operator<(T a, T b)
{
return 0;
}
signed main()
{
#ifdef ONPC
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
cin >> k >> cntcols >> cntrows;
for (int i = 1; i <= cntrows; i++)
{
string str;
cin >> str;
assert((int)str.size() == cntcols);
for (int j = 1; j <= cntcols; j++)
{
char ch = str[j - 1];
if ('1' <= ch && ch <= '9')
{
a[i][j] = ch - '0';
assert(1 <= a[i][j] && a[i][j] <= 9);
continue;
}
if (ch == '.')
{
a[i][j] = 0;
continue;
}
if (ch == 'x')
{
a[i][j] = -1;
continue;
}
a[i][j] = 0;
assert(ch == 'A' || ch == 'C');
if (ch == 'A')
{
adddir[i][j] = 3;
}
else
{
assert(ch == 'C');
adddir[i][j] = 1;
}
}
}
for (int i = 1; i <= cntrows; i++)
{
for (int j = 1; j <= cntcols; j++)
{
for (int k = 0; k < 4; k++)
{
w[i][j][k] = go(i, j, k);
}
for (int l = 1; l <= k; l++)
{
for (int r = l; r <= k; r++)
{
dp[i][j][l][r] = INF;
}
}
if (a[i][j] >= 1)
{
assert(1 <= a[i][j] && a[i][j] <= k);
dp[i][j][a[i][j]][a[i][j]] = 0;
}
}
}
//{
// int r = 5, c = 5;
// cout << w[r][c][1].first << " " << w[r][c][1].second << "\n";
// exit(0);
//}
for (int st = k; st >= 1; st--)
{
for (int dr = st; dr <= k; dr++)
{
for (int mij = st; mij < dr; mij++)
{
for (int i = 1; i <= cntrows; i++)
{
for (int j = 1; j <= cntcols; j++)
{
dp[i][j][st][dr] = min(dp[i][j][st][dr], dp[i][j][st][mij] + dp[i][j][mij + 1][dr]);
}
}
}
priority_queue<pair<int, T>> pq;
for (int i = 1; i <= cntrows; i++)
{
for (int j = 1; j <= cntcols; j++)
{
pq.push({ -dp[i][j][st][dr], {i, j, st, dr} });
}
}
while (!pq.empty())
{
auto it = pq.top();
pq.pop();
it.first *= -1;
int i = it.second.i;
int j = it.second.j;
int st = it.second.st;
int dr = it.second.dr;
if (dp[i][j][st][dr] != it.first)
{
continue;
}
for (int k = 0; k < 4; k++)
{
int in = w[i][j][k].first, jn = w[i][j][k].second;
if (dp[i][j][st][dr] + 1 < dp[in][jn][st][dr])
{
dp[in][jn][st][dr] = dp[i][j][st][dr] + 1;
pq.push({-dp[in][jn][st][dr], { in, jn, st, dr } });
}
}
}
continue;
vector<pair<int, T>> v;
for (int i = 1; i <= cntrows; i++)
{
for (int j = 1; j <= cntcols; j++)
{
if (dp[i][j][st][dr] < INF)
{
v.push_back({ dp[i][j][st][dr], {i, j, st, dr} });
}
}
}
sort(v.begin(), v.end(), [&](pair<int, T> a, pair<int, T> b) {return a.first < b.first; });
int pos = 0;
vector<T> waiting;
while (1)
{
queue<T> q;
if (waiting.empty())
{
if (pos == (int)v.size())
{
break;
}
assert(pos < (int)v.size());
int what = v[pos].first;
while (pos < (int)v.size() && v[pos].first == what)
{
q.push(v[pos++].second);
}
}
else
{
if (pos < (int)v.size())
{
auto& it = waiting[0];
int what = dp[it.i][it.j][it.st][it.dr];
assert(what <= v[pos].first);
while (pos < (int)v.size() && v[pos].first == what)
{
q.push(v[pos++].second);
}
}
else
{
assert(pos == (int)v.size());
}
}
while (!waiting.empty())
{
q.push(waiting.back());
waiting.pop_back();
}
while (!q.empty())
{
if (q.empty())
{
break;
}
auto it = q.front();
q.pop();
int i = it.i, j = it.j, st = it.st, dr = it.dr;
for (int k = 0; k < 4; k++)
{
int in = w[i][j][k].first, jn = w[i][j][k].second;
if (dp[i][j][st][dr] + 1 < dp[in][jn][st][dr])
{
dp[in][jn][st][dr] = 1 + dp[i][j][st][dr];
waiting.push_back({ in, jn, st, dr });
}
}
}
}
}
}
int sol = INF;
for (int i = 1; i <= cntrows; i++)
{
for (int j = 1; j <= cntcols; j++)
{
sol = min(sol, dp[i][j][1][k]);
}
}
cout << sol << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
