oj.uz

Submission #40404

# Submission time Handle Problem Language Result Execution time Memory
40404 2018-02-01T06:41:24 Z mohammad_kilani Robots (APIO13_robots) C++14
30 / 100
 412 ms 33436 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000000
const double PI = acos(-1);
const int N = 501;
char grid[N][N];
int n , m , sr , sc, cnt = 0 , idx[10][10] , num , vis[N][N] , vi = 1 , row , col , nr ,nc , 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< pair<int,pair<int,int> > > tmp;

deque < pair<int,int> > q;

inline void BFS(int low,int high){
	vi++;
	tmp.clear();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			tmp.push_back(make_pair(best[idx[low][high]][i][j],make_pair(i,j)));
		}
	}
	sort(tmp.begin(),tmp.end());
	int cost = tmp[0].first;
	for(int i=0;i<tmp.size();i++){
		q.push_back(tmp[i].second);
		while(!q.empty()){
			row = q.back().first;
			col = q.back().second;
			q.pop_back();
			if(vis[row][col] == vi) continue;
			vis[row][col] = vi;
			while(i + 1 < tmp.size() && tmp[i + 1].first == best[idx[low][high]][row][col]){
				i++;
				if(vis[tmp[i].second.first][tmp[i].second.second] == vi) continue;
				vis[tmp[i].second.first][tmp[i].second.second] = vi;
				q.push_back(tmp[i].second);
			}
			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(nr,nc));
				best[idx[low][high]][nr][nc] = min(best[idx[low][high]][row][col] + 1,best[idx[low][high]][nr][nc]);
			}
		}
	}
}
 
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:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
               ^
robots.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i + 1 < tmp.size() && tmp[i + 1].first == best[idx[low][high]][row][col]){
                ^
robots.cpp:25:6: warning: unused variable 'cost' [-Wunused-variable]
  int cost = tmp[0].first;
      ^
robots.cpp: In function 'int main()':
robots.cpp:70: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:79: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 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 660 KB Output is correct
4 Correct 2 ms 1428 KB Output is correct
5 Correct 2 ms 1428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 660 KB Output is correct
4 Correct 2 ms 1428 KB Output is correct
5 Correct 2 ms 1428 KB Output is correct
6 Correct 2 ms 1428 KB Output is correct
7 Correct 2 ms 1428 KB Output is correct
8 Correct 2 ms 1428 KB Output is correct
9 Correct 2 ms 1428 KB Output is correct
10 Correct 3 ms 1700 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 660 KB Output is correct
4 Correct 2 ms 1428 KB Output is correct
5 Correct 2 ms 1428 KB Output is correct
6 Correct 2 ms 1428 KB Output is correct
7 Correct 2 ms 1428 KB Output is correct
8 Correct 2 ms 1428 KB Output is correct
9 Correct 2 ms 1428 KB Output is correct
10 Correct 3 ms 1700 KB Output is correct
11 Incorrect 412 ms 33436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 660 KB Output is correct
4 Correct 2 ms 1428 KB Output is correct
5 Correct 2 ms 1428 KB Output is correct
6 Correct 2 ms 1428 KB Output is correct
7 Correct 2 ms 1428 KB Output is correct
8 Correct 2 ms 1428 KB Output is correct
9 Correct 2 ms 1428 KB Output is correct
10 Correct 3 ms 1700 KB Output is correct
11 Incorrect 412 ms 33436 KB Output isn't correct
12 Halted 0 ms 0 KB -