oj.uz

답안 #40359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40359 2018-01-31T11:46:37 Z mohammad_kilani 로봇 (APIO13_robots) C++14
0 / 100
 30 ms 39780 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));
		}
		
	}
 	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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 39672 KB Output is correct
2 Incorrect 29 ms 39780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 39672 KB Output is correct
2 Incorrect 29 ms 39780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 39672 KB Output is correct
2 Incorrect 29 ms 39780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 39672 KB Output is correct
2 Incorrect 29 ms 39780 KB Output isn't correct
3 Halted 0 ms 0 KB -