Submission #278069

#	Time	Username	Problem	Language	Result	Execution time	Memory
278069		petar_vitorac	Awesome Arrowland Adventure (eJOI19_adventure)	C++11	100 / 100	158 ms	7784 KiB

adventure

#include<bits/stdc++.h>
using namespace std;

enum class Location {
	Upper = 1,
	Left = 2,
	Lower = 3,
	Right = 4
};

enum class Orientation {
	X = -1, //empty
	S = 1, //south
	E = 2, //east
	N = 3, //north
	W = 4 //west
};

struct Coord {
	int x, y;
	
	Coord(int a = 0, int b = 0) : x(a), y(b) {};
	
	bool operator<(const Coord &other) const {
    	if (x < other.x) return true;
    	else if (x > other.x) return false;
    	else return y < other.y;
	}
};

struct Cell {
	Coord coord;
	Orientation orientation;
	
	Cell(Coord a = Coord(), Orientation b = Orientation::X) : coord(a), orientation(b) {};
};


struct Neighbor {
	Coord coord;
	int distance;
	
	Neighbor(Coord a = Coord(), int b = 0) : coord(a), distance(b) {};
};

vector<vector<Cell>> grid;
int M, N;
vector<vector<int>> dist;

Orientation getOrientation (char charorientation) {
	switch (charorientation) {
		case 'S':
			return Orientation::S;
		case 'E':
			return Orientation::E;
		case 'N':
			return Orientation::N;
		case 'W':
			return Orientation::W;
		default:
			return Orientation::X;
	}
}

int distToNeigh(Location location, Orientation orientation) {
	return (((int)orientation - (int)location)+4)%4;
}


void checkNeigh(Coord curr, Location neighLocation, vector<Neighbor> &result) {
	bool exists;
	Coord neighCoord;
	
	switch(neighLocation) {
		case Location::Upper:
			exists = (curr.y > 0);
			neighCoord = Coord(curr.x, curr.y - 1);
			break;
			
		case Location::Left:
			exists = (curr.x > 0);
			neighCoord = Coord(curr.x - 1, curr.y);
			break;
			
		case Location::Lower:
			exists = (curr.y < M - 1);
			neighCoord = Coord(curr.x, curr.y + 1);
			break;
			
		case Location::Right:
			exists = (curr.x < N - 1);
			neighCoord = Coord(curr.x + 1, curr.y);
			break;
			
		default:
			exists = false;
			break;
	}
	
	
	
	if(exists) {
		Cell neighCell = grid[neighCoord.x][neighCoord.y];
		
		if(neighCell.orientation != Orientation::X) {
			result.push_back(Neighbor(neighCoord, distToNeigh(neighLocation, neighCell.orientation)));
		}
	}
}

vector<Neighbor> getNeigh(Coord curr) {
	vector<Neighbor> result;
	
	for(int i = 1; i <= 4; i++) {
		checkNeigh(curr, (Location)i, result);
	}
	
	return result;
}

void dijkastra() {
	dist[N-1][M-1] = 0;
	
	vector<vector<bool>> done (N, vector<bool>(M));
	
	priority_queue<pair<int, Coord>> q;
	q.push({0, Coord(N-1, M-1)});
	
	
	while(!q.empty()){
		Coord curr = q.top().second; q.pop();
		
		if(!done[curr.x][curr.y]) {
			done[curr.x][curr.y] = true;
			
			vector<Neighbor> neighs = getNeigh(curr);
			
			for(Neighbor neigh : neighs) {
				if(dist[curr.x][curr.y] + neigh.distance < dist[neigh.coord.x][neigh.coord.y] || dist[neigh.coord.x][neigh.coord.y] == -1) {
					dist[neigh.coord.x][neigh.coord.y] = dist[curr.x][curr.y] + neigh.distance;
					q.push({-dist[neigh.coord.x][neigh.coord.y], neigh.coord});
				}
			}
		}
	}
}

int main() {
	cin >> M >> N;
	
	grid.resize(N, vector<Cell>(M));
	dist.resize(N, vector<int>(M, -1));
	
	for(int y = 0; y < M; y++) {
		string row; cin >> row;
		for(int x = 0; x < N; x++) {
			grid[x][y] = Cell(Coord(x, y), getOrientation(row[x]));
		}
	}
	
	dijkastra();
	
	cout << dist[0][0] << "\n";
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50