oj.uz

Submission #40361

# Submission time Handle Problem Language Result Execution time Memory
40361 2018-01-31T11:59:48 Z mohammad_kilani Robots (APIO13_robots) C++14
30 / 100
 78 ms 87696 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 , l ,r , cost , row , col , best[40][N][N];
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};
pair<int,int> nxt[N][N][4];

struct Node{
	int l , r , cost , row, col;
	Node(int a,int b,int c,int d,int e){
		l = a, r = b, cost = c, row = d,col = e;
	}
	bool operator<(const Node other) const {
		return cost > other.cost;
	}
};

priority_queue < Node> q;

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(){
	memset(best,-1,sizeof(best));
	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<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'){
				q.push(Node(grid[i][j]-'0',grid[i][j]-'0',0,i,j));
			}
			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);
				}
			}
		}
	}
	while(!q.empty()){
		row = q.top().row;
		col = q.top().col;
		cost = q.top().cost;
		l = q.top().l;
		r = q.top().r;
		q.pop();
		if(best[idx[l][r]][row][col] != -1) continue;
		best[idx[l][r]][row][col] = cost;
		if(l == 1 && r == num){
			cout << cost << endl;
			return 0;
		}
		for(int i=1;i<l;i++){
			if(best[idx[i][l-1]][row][col] == -1 || best[idx[i][r]][row][col] != -1) continue;
			q.push(Node(i,r,cost + best[idx[i][l-1]][row][col],row,col));
		}
		for(int i=r+1;i<=num;i++){
			if(best[idx[r+1][i]][row][col] == -1 || best[idx[l][i]][row][col] != -1) continue;
			q.push(Node(l,i,cost + best[idx[r+1][i]][row][col],row,col));
		}
		for(int i=0;i<4;i++){
			if(nxt[row][col][i] == make_pair(-1,-1) || best[idx[l][r]][nxt[row][col][i].first][nxt[row][col][i].second] != -1) continue;
			q.push(Node(l,r,cost + 1,nxt[row][col][i].first,nxt[row][col][i].second));
		}
		
	}
	cout << -1 << endl;
 	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:45: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:47: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 29 ms 39676 KB Output is correct
2 Correct 29 ms 39676 KB Output is correct
3 Correct 29 ms 39720 KB Output is correct
4 Correct 35 ms 39828 KB Output is correct
5 Correct 31 ms 39832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39676 KB Output is correct
2 Correct 29 ms 39676 KB Output is correct
3 Correct 29 ms 39720 KB Output is correct
4 Correct 35 ms 39828 KB Output is correct
5 Correct 31 ms 39832 KB Output is correct
6 Correct 29 ms 39836 KB Output is correct
7 Correct 30 ms 39968 KB Output is correct
8 Correct 30 ms 39968 KB Output is correct
9 Correct 29 ms 39996 KB Output is correct
10 Correct 35 ms 39996 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39676 KB Output is correct
2 Correct 29 ms 39676 KB Output is correct
3 Correct 29 ms 39720 KB Output is correct
4 Correct 35 ms 39828 KB Output is correct
5 Correct 31 ms 39832 KB Output is correct
6 Correct 29 ms 39836 KB Output is correct
7 Correct 30 ms 39968 KB Output is correct
8 Correct 30 ms 39968 KB Output is correct
9 Correct 29 ms 39996 KB Output is correct
10 Correct 35 ms 39996 KB Output is correct
11 Runtime error 78 ms 87696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39676 KB Output is correct
2 Correct 29 ms 39676 KB Output is correct
3 Correct 29 ms 39720 KB Output is correct
4 Correct 35 ms 39828 KB Output is correct
5 Correct 31 ms 39832 KB Output is correct
6 Correct 29 ms 39836 KB Output is correct
7 Correct 30 ms 39968 KB Output is correct
8 Correct 30 ms 39968 KB Output is correct
9 Correct 29 ms 39996 KB Output is correct
10 Correct 35 ms 39996 KB Output is correct
11 Runtime error 78 ms 87696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -