Tävlingsprogrammering/Uppgifter/Skridskor
Se skridskoplanen som en graf där du vill hitta kortaste vägen ut. Alltså är det ett SSSP problem där vi kan använda en BFS sökning för att hitta svaret i O(V+E).
Notera att lösningen nedan är O(E log V) snarare än O(E), eftersom operationerna på dist (som är en map) tar tid O(log V).
Lösning av Andreas Wallström:
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <string.h>
#include <tuple>
#include <map>
#define DIR_U 0
#define DIR_R 1
#define DIR_D 2
#define DIR_L 3
using namespace std;
int R, C;
vector<vector<char>> theMap;
int main() {
ios_base::sync_with_stdio(false); // Speedar upp cin till scanf() nivåer ;)
char entity;
cin >> R >> C;
theMap.assign(R, vector<char>(C));
for(int y = 0; y < R; y++) {
for(int x = 0; x < C; x++) {
cin >> entity;
theMap[y][x] = entity;
}
}
map<pair<int, int>, long long int> dist;
dist[make_pair(0, 0)] = 0;
queue<tuple<int, int, int>> q;
q.push(make_tuple(0, 0, DIR_R)); //(y, x, dir)
// DFS börjar här
while(!q.empty()) {
tuple<int, int, int> u = q.front();
q.pop();
int oldY = get<0>(u);
int oldX = get<1>(u);
int dir = get<2>(u);
// Din nya riktning kommer alltid att vara +90 och -90 grader från den du har nu
int newDir1 = ((dir + 1) % 4);
int newDir2 = ((dir == 0) ? 3 : dir - 1);
int newX = -1, newY = -1;
// Gå åt de håll hon åker, gå tills du stöter på ett hinder (#). Det blir din nya position
switch(dir) {
case DIR_R:
for(int x = oldX; x <= C; x++) { // Scanna hela vägen åt höger efter ett hinder (#)
if(theMap[oldY][x] == '#') {
newX = x-1;
newY = oldY;
break;
}
else if(x == C-1) {
// Klar, skriv ut svaret! (man kommer alltid åka ut på höger sida)
cout << dist[make_pair(oldY, oldX)] << endl;
return 0;
}
}
break;
case DIR_D:
for(int y = oldY; y < R; y++) { // Scanna hela vägen neråt efter ett hinder (#)
if(theMap[y][oldX] == '#') {
newX = oldX;
newY = y-1;
break;
}
}
break;
case DIR_L: // Scanna hela vägen åt vänster efter ett hinder (#)
for(int x = oldX; x >= 0; x--) {
if(theMap[oldY][x] == '#') {
newX = x+1;
newY = oldY;
break;
}
}
break;
case DIR_U: // Scanna hela vägen uppåt efter ett hinder (#)
for(int y = oldY; y >= 0; y--) {
if(theMap[y][oldX] == '#') {
newX = oldX;
newY = y+1;
break;
}
}
break;
}
if(newX == -1 || newY == -1) {
continue;
}
//newX == 0 && newY == 0 är ett edge case
if(dist.find(make_pair(newY, newX)) == dist.end() || newX == 0 && newY == 0) {
dist[make_pair(newY, newX)] = dist[make_pair(oldY, oldX)] + 1;
q.push(make_tuple(newY, newX, newDir1));
q.push(make_tuple(newY, newX, newDir2));
}
}
}