#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;
FILE *f = fopen("robots.in","r");
FILE *g = fopen("robots.out","w");
int n,w,h;
int dp[505][505][9][9];
pair<int,int> where_do_i_end[505][505][4];
char C[505][505];
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int inf = 1 << 28;
queue< pair<int,int> > Q;
bool inQ[505][505];
void push(int x,int y){
if(!inQ[x][y]){
Q.push({x,y});
inQ[x][y] = 1;
}
}
void solve(int st,int dr){
while(!Q.empty()){
pair<int,int> pos = Q.front();
Q.pop();
inQ[pos.first][pos.second] = 0;
for(int k = 0;k < 4;k++){
pair<int,int> npos = where_do_i_end[pos.first][pos.second][k];
if(npos.first == -1 && npos.second == -1){
continue;
}
if(dp[npos.first][npos.second][st][dr] > dp[pos.first][pos.second][st][dr] + 1){
dp[npos.first][npos.second][st][dr] = dp[pos.first][pos.second][st][dr] + 1;
if(!inQ[npos.first][npos.second]){
Q.push(npos);
inQ[npos.first][npos.second] = 1;
}
}
}
}
}
int which_viz[505][505][4];
int last_viz;
pair<int,int> get_end(int i,int j,int k){
if(where_do_i_end[i][j][k].first || where_do_i_end[i][j][k].second){
return where_do_i_end[i][j][k];
}
where_do_i_end[i][j][k] = {i,j};
vector< pair<pair<int,int>,int> > V = {make_pair(make_pair(i,j),k)};
which_viz[i][j][k] = ++last_viz;
pair<int,int> ans = {-1,-1};
for(int k = 0;k < (int)V.size();k++){
int dir = (V[k].second + (C[V[k].first.first][V[k].first.second] == 'C') + (C[V[k].first.first][V[k].first.second] == 'A' ? 3:0)) & 3;
int x = V[k].first.first + dx[dir];
int y = V[k].first.second + dy[dir];
if(!(x && y && x <= h && y <= w && C[x][y] != '#')){
ans = V[k].first;
break;
}
else if(!which_viz[x][y][dir]){
V.push_back({{x,y},dir});
which_viz[x][y][dir] = last_viz;
}
else{
if(which_viz[x][y][dir] != last_viz){
ans = where_do_i_end[x][y][dir];
}
else{
break;
}
}
}
for(auto it:V){
where_do_i_end[it.first.first][it.first.second][it.second] = ans;
}
return where_do_i_end[i][j][k];
}
int main(){
fscanf(f,"%d %d %d\n",&n,&w,&h);
for(int i = 1;i <= h;i++){
fgets(C[i] + 1,w + 1,f);
}
// for(int i = 1;i <= h;i++ ){
// for(int j = 1;j <= w;j++){
// for(int k = 0;k < 4;k++){
// where_do_i_end[i][j][k] = get_end(i,j,k);
// }
// }
// }
// for(int i = 1;i <= h;i++){
// for(int j = 1;j <= w;j++){
// for(int st = 0;st < n;st++){
// for(int dr = 0;dr < n;dr++){
// dp[i][j][st][dr] = inf;
// }
// }
// if('1' <= C[i][j] && C[i][j] <= '9'){
// dp[i][j][C[i][j] - '1'][C[i][j] - '1'] = 0;
// push(i,j);
// solve(C[i][j] - '1',C[i][j] - '1');
// }
// }
// }
// for(int l = 1;l < 9;l++){
// for(int st = 0;st < n;st++){
// int dr = st + l;
// for(int i = 1;i <= h;i++){
// for(int j = 1;j <= w;j++){
// for(int k = st;k < dr;k++){
// dp[i][j][st][dr] = min(dp[i][j][st][k] + dp[i][j][k + 1][dr],dp[i][j][st][dr]);
// }
// push(i,j);
// }
// }
// solve(st,dr);
// }
// }
// int ans = inf;
// for(int i = 1;i <= h;i++){
// for(int j = 1;j <= w;j++){
// if(ans > dp[i][j][0][n - 1]){
// ans = dp[i][j][0][n - 1];
// }
// }
// }
// printf("%d",sizeof(dp) + sizeof(where_do_i_end) + sizeof(which_viz));
// fprintf(g,"%d\n",(ans == inf ? -1:ans));
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:100:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(f,"%d %d %d\n",&n,&w,&h);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:103:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fgets(C[i] + 1,w + 1,f);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
