| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 77309 |
2018-09-25T05:54:55 Z |
ekrem |
Robots (APIO13_robots) |
C++ |
|
100 ms |
118216 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 505
using namespace std;
typedef pair < int , int > ii;
int n, m, k, a[N][N], d[10][N][N], u[10][N][N], dp[10][10][N][N];
ii git[4][N][N];
int o[] = {-1, 0, 1, 0};
int p[] = {0, 1, 0, -1};
char x;
inline bool bak(int i, int j){return !(i > n or j > m or i < 1 or j < 1 or a[i][j] == -1);}
ii gt(int i, int j, int yon){
ii &r = git[yon][i][j];
if(r.st != -1)
return r;
r = mp(inf, inf);
if(!bak(i + o[yon], j + p[yon]))
return r = mp(i, j);
if(a[i][j] == -2)
return r = gt(i + o[(yon + 1)%4], j + p[(yon + 1)%4], (yon + 1)%4);
if(a[i][j] == -3)
return r = gt(i + o[(yon + 3)%4], j + p[(yon + 3)%4], (yon + 3)%4);
return r = gt(i + o[yon], j + p[yon], yon);
}
void bul(int k){
int x, y;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(a[i][j] == k){
x = i;
y = j;
break;
}
priority_queue < pair < int , ii > > b;
d[k][x][y] = 0;
b.push(mp(0, mp(x, y)));
while(!b.empty()){
int yol = -b.top().st;
int x = b.top().nd.st;
int y = b.top().nd.nd;
b.pop();
u[k][x][y] = 1;
for(int z = 0; z < 4; z++){
ii g = gt(x, y, z);
d[k][g.st][g.nd] = min(d[k][g.st][g.nd], yol + 1);
if(!u[k][g.st][g.nd])
b.push(mp(-d[k][g.st][g.nd], mp(g.st, g.nd)));
}
}
}
int f(int a, int b, int x, int y){
int &r = dp[a][b][x][y];
if(r != -1)
return r;
r = inf;
if(a > b)
return r = 0;
if(a == b)
return r = d[a][x][y];
for(int i = a; i < b; i++)
r = min(r, f(a, i, x, y) + f(i + 1, b, x, y));
return 0;
}
int main() {
freopen("in.txt", "r", stdin);
freopen("outt.txt", "w", stdout);
memset(git, -1, sizeof git);
memset(dp, -1, sizeof dp);
memset(d, 20, sizeof d);
scanf("%d %d %d",&k ,&m ,&n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
scanf(" %c",&x);
if(x == 'x')
a[i][j] = -1;
else if(x == '.')
a[i][j] = 0;
else if(x == 'C')
a[i][j] = -2;
else if(x == 'A')
a[i][j] = -3;
else
a[i][j] = x - '0';
}
for(int i = 1; i <= k; i++)
bul(i);
// cout << d[1][3][1] << endl;
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("in.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:77:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("outt.txt", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&k ,&m ,&n);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&x);
~~~~~^~~~~~~~~~
robots.cpp: In function 'void bul(int)':
robots.cpp:45:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
b.push(mp(0, mp(x, y)));
^
robots.cpp:45:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
118216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
118216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
118216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
118216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
