Tävlingsprogrammering/Uppgifter/Skridskor

Från Wikibooks
Hoppa till navigering Hoppa till sök

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));
        }
    }
}