oj.uz

Submission #40362

# Submission time Handle Problem Language Result Execution time Memory
40362 2018-01-31T12:00:49 Z mohammad_kilani Robots (APIO13_robots) C++14
30 / 100
 1500 ms 95312 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[50][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 37 ms 49400 KB Output is correct
2 Correct 36 ms 49632 KB Output is correct
3 Correct 36 ms 49632 KB Output is correct
4 Correct 36 ms 49648 KB Output is correct
5 Correct 37 ms 49648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49400 KB Output is correct
2 Correct 36 ms 49632 KB Output is correct
3 Correct 36 ms 49632 KB Output is correct
4 Correct 36 ms 49648 KB Output is correct
5 Correct 37 ms 49648 KB Output is correct
6 Correct 36 ms 49648 KB Output is correct
7 Correct 36 ms 49648 KB Output is correct
8 Correct 37 ms 49680 KB Output is correct
9 Correct 37 ms 49740 KB Output is correct
10 Correct 36 ms 49752 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49400 KB Output is correct
2 Correct 36 ms 49632 KB Output is correct
3 Correct 36 ms 49632 KB Output is correct
4 Correct 36 ms 49648 KB Output is correct
5 Correct 37 ms 49648 KB Output is correct
6 Correct 36 ms 49648 KB Output is correct
7 Correct 36 ms 49648 KB Output is correct
8 Correct 37 ms 49680 KB Output is correct
9 Correct 37 ms 49740 KB Output is correct
10 Correct 36 ms 49752 KB Output is correct
11 Correct 1033 ms 74540 KB Output is correct
12 Correct 43 ms 74540 KB Output is correct
13 Correct 47 ms 74540 KB Output is correct
14 Execution timed out 1550 ms 95312 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49400 KB Output is correct
2 Correct 36 ms 49632 KB Output is correct
3 Correct 36 ms 49632 KB Output is correct
4 Correct 36 ms 49648 KB Output is correct
5 Correct 37 ms 49648 KB Output is correct
6 Correct 36 ms 49648 KB Output is correct
7 Correct 36 ms 49648 KB Output is correct
8 Correct 37 ms 49680 KB Output is correct
9 Correct 37 ms 49740 KB Output is correct
10 Correct 36 ms 49752 KB Output is correct
11 Correct 1033 ms 74540 KB Output is correct
12 Correct 43 ms 74540 KB Output is correct
13 Correct 47 ms 74540 KB Output is correct
14 Execution timed out 1550 ms 95312 KB Time limit exceeded
15 Halted 0 ms 0 KB -