oj.uz

Submission #40408

# Submission time Handle Problem Language Result Execution time Memory
40408 2018-02-01T07:12:05 Z mohammad_kilani Robots (APIO13_robots) C++14
100 / 100
 731 ms 65792 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000000
const double PI = acos(-1);
const int N = 501 , MAX_COST = 500 * 75 * 9 + 1;
char grid[N][N];
int n , m , sr , sc, cnt = 0 , idx[10][10] , num , vis[N][N] , vi = 1 , row , col , nr ,nc , cost , best[50][N][N];
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};
pair<int,int> nxt[N][N][4]; 
vector< vector< pair<int,int> > > tmp2;
vector< pair<int,pair<int,int> > > tmp;
deque < pair<int, pair<int,int> > > q;

inline void BFS(int low,int high){
	vi++;
	tmp.clear();
	tmp2.clear();
	tmp2.resize(MAX_COST);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(best[idx[low][high]][i][j] == oo) continue;
			tmp2[best[idx[low][high]][i][j]].push_back(make_pair(i,j));
		}
	}
	for(int i=0;i<MAX_COST;i++)
		for(int j=0;j<tmp2[i].size();j++){
			tmp.push_back(make_pair(i,tmp2[i][j]));
		}
	for(int i=0;i<tmp.size();i++){
		q.push_back(tmp[i]);
		while(!q.empty()){
			cost = q.back().first;
			row = q.back().second.first;
			col = q.back().second.second;
			q.pop_back();
			if(vis[row][col] == vi) continue;
			vis[row][col] = vi;
			best[idx[low][high]][row][col] = cost;
			while(i + 1 < tmp.size() && tmp[i + 1].first == cost){
				i++;
				if(vis[tmp[i].second.first][tmp[i].second.second] == vi) continue;
				q.push_back(tmp[i]);
			}
			for(int i=0;i<4;i++){
				nr = nxt[row][col][i].first;
				nc = nxt[row][col][i].second;
				if(nr == -1 || vis[nr][nc] == vi) continue;
				q.push_front(make_pair(cost + 1 , make_pair(nr,nc)));
			}
		}
	}
}
 
inline void make(int r,int c,int k){
	sr = r;
	sc = c;
	while(r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != 'x'){
		if(grid[r][c] == 'A') k--; else if(grid[r][c] == 'C') k++;
		if(k == -1) k = 3;
		if(k == 4) k = 0;
		nxt[r][c][k] = make_pair(sr,sc);
		r = r + dr[k];
		c = c + dc[k];
	}
}
 
int main(){
	for(int i=1;i<10;i++){
		for(int j=i;j<10;j++){
			idx[i][j] = cnt++;
		}
	}
	scanf("%d%d%d",&num,&m,&n);
	for(int i=0;i<cnt;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<m;k++){
				best[i][j][k] = oo;
			}
		}
	}
	for(int i=0;i<n;i++)
		scanf("%s",grid[i]);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(grid[i][j] >= '1' && grid[i][j] <= '9'){
				best[idx[grid[i][j]-'0'][grid[i][j]-'0']][i][j] = 0;
			}
			for(int k=0;k<4;k++)
				nxt[i][j][k] = make_pair(-1,-1);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(grid[i][j] == 'x') continue;
			sr = i;
			sc = j;
			for(int k=0;k<4;k++){
				int nr = i + dr[k];
				int nc = j + dc[k];
				if(nr == -1 || nr == n || nc == -1 || nc == m || grid[nr][nc] == 'x'){
					make(i,j,(k + 2) % 4);
				}
			}
		}
	}
	for(int i=0;i<num;i++){
		for(int j=1;j+i<=num;j++){
			for(int row=0;row<n;row++){
				for(int col=0;col<m;col++){
					for(int k=j;k<j+i;k++){
						best[idx[j][i+j]][row][col] = min(best[idx[j][i+j]][row][col],best[idx[j][k]][row][col] + best[idx[k+1][i+j]][row][col]);
					}
				}
			}
			BFS(j,j+i);
		}
	}
	int ans = oo;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			ans = min(ans,best[idx[1][num]][i][j]);
		}
	}
	if(ans == oo) ans = -1;
	cout << ans << endl;
 	return 0;
}

Compilation message

robots.cpp: In function 'void BFS(int, int)':
robots.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<tmp2[i].size();j++){
                ^
robots.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
               ^
robots.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i + 1 < tmp.size() && tmp[i + 1].first == cost){
                ^
robots.cpp: In function 'int main()':
robots.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&num,&m,&n);
                            ^
robots.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",grid[i]);
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 11 ms 8672 KB Output is correct
3 Correct 11 ms 8676 KB Output is correct
4 Correct 25 ms 9560 KB Output is correct
5 Correct 12 ms 9560 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 11 ms 8672 KB Output is correct
3 Correct 11 ms 8676 KB Output is correct
4 Correct 25 ms 9560 KB Output is correct
5 Correct 12 ms 9560 KB Output is correct
6 Correct 11 ms 9560 KB Output is correct
7 Correct 12 ms 9560 KB Output is correct
8 Correct 13 ms 9560 KB Output is correct
9 Correct 11 ms 9560 KB Output is correct
10 Correct 11 ms 9580 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 11 ms 8672 KB Output is correct
3 Correct 11 ms 8676 KB Output is correct
4 Correct 25 ms 9560 KB Output is correct
5 Correct 12 ms 9560 KB Output is correct
6 Correct 11 ms 9560 KB Output is correct
7 Correct 12 ms 9560 KB Output is correct
8 Correct 13 ms 9560 KB Output is correct
9 Correct 11 ms 9560 KB Output is correct
10 Correct 11 ms 9580 KB Output is correct
11 Correct 216 ms 40744 KB Output is correct
12 Correct 33 ms 40744 KB Output is correct
13 Correct 93 ms 40744 KB Output is correct
14 Correct 347 ms 41132 KB Output is correct
15 Correct 164 ms 41132 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 11 ms 8672 KB Output is correct
3 Correct 11 ms 8676 KB Output is correct
4 Correct 25 ms 9560 KB Output is correct
5 Correct 12 ms 9560 KB Output is correct
6 Correct 11 ms 9560 KB Output is correct
7 Correct 12 ms 9560 KB Output is correct
8 Correct 13 ms 9560 KB Output is correct
9 Correct 11 ms 9560 KB Output is correct
10 Correct 11 ms 9580 KB Output is correct
11 Correct 216 ms 40744 KB Output is correct
12 Correct 33 ms 40744 KB Output is correct
13 Correct 93 ms 40744 KB Output is correct
14 Correct 347 ms 41132 KB Output is correct
15 Correct 164 ms 41132 KB Output is correct
16 Correct 289 ms 61436 KB Output is correct
17 Correct 731 ms 65792 KB Output is correct
18 Correct 297 ms 65792 KB Output is correct
19 Correct 238 ms 65792 KB Output is correct
20 Correct 677 ms 65792 KB Output is correct