제출 #364646

#제출 시각아이디문제언어결과실행 시간메모리
364646parsabahrami로봇 (APIO13_robots)C++17
100 / 100
1287 ms117108 KiB
// Call my Name and Save me from The Dark #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 5e2 + 10, MOD = 1e9 + 7; int M[N][N], shit[4][N][N], dp[10][10][N][N], n, m, k; pii G[4][N][N]; // wtf is this char A[N][N]; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; pii go(int x, int y, int d) { if (~G[d][x][y].F) return G[d][x][y]; if (shit[d][x][y]) return G[d][x][y] = {-1, -1}; int nxt = d; shit[d][x][y] = 1; if (A[x][y] == 'A') nxt = (nxt + 1) % 4; if (A[x][y] == 'C') nxt = (nxt - 1 + 4) % 4; int nx = dx[nxt] + x, ny = dy[nxt] + y; if (nx <= 0 || nx > n || ny > m || ny <= 0 || A[nx][ny] == 'x') return G[d][x][y] = {x, y}; return G[d][x][y] = go(nx, ny, nxt); } int main() { for (int i = 0; i < 4; i++) for (int j = 0; j < N; j++) for (int l = 0; l < N; l++) G[i][j][l] = {-1, -1}; scanf("%d%d%d", &k, &m, &n); for (int i = 1; i <= n; i++) { scanf("%s", A[i] + 1); } for (int l = 0; l < 10; l++) for (int r = 0; r < 10; r++) for (int i = 0; i < N; i++) fill(dp[l][r][i], dp[l][r][i] + N, MOD); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (A[i][j] != 'x') for (int d = 0; d < 4; d++) go(i, j, d); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (A[i][j] != 'x' && A[i][j] != '.' && A[i][j] != 'A' && A[i][j] != 'C') dp[A[i][j] - '0'][A[i][j] - '0'][i][j] = 0; } } for (int sz = 1; sz <= k; sz++) { for (int l = 1; l + sz - 1 <= k; l++) { int r = l + sz - 1; deque<pii> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int t = l; t < r; t++) dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][t][i][j] + dp[t + 1][r][i][j]); if (dp[l][r][i][j] < MOD) q.push_back({i, j}); } } sort(q.begin(), q.end(), [&] (pii x, pii y) { return dp[l][r][x.F][x.S] < dp[l][r][y.F][y.S]; }); while (SZ(q)) { int x = q.front().F, y = q.front().S; q.pop_front(); M[x][y] = 0; for (int d = 0; d < 4; d++) { if (~G[d][x][y].F) { int nx = G[d][x][y].F, ny = G[d][x][y].S; if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) { dp[l][r][nx][ny] = dp[l][r][x][y] + 1; if (M[nx][ny]) continue; M[nx][ny] = 1; q.push_back({nx, ny}); } } } } } } int ret = MOD; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ret = min(ret, dp[1][k][i][j]); printf("%d\n", ret == MOD ? -1 : ret); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'int main()':
robots.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d%d", &k, &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         scanf("%s", A[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...