Untitled

 avatar
unknown
plain_text
a month ago
17 kB
5
Indexable
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#ifdef _WIN32
  #include <windows.h>  // for Sleep()
  #define SLEEP(ms) Sleep(ms)
#else
  #include <unistd.h>   // for usleep()
  #define SLEEP(ms) usleep((ms)*1000)
#endif

// -----------------------------------------------------------------------------
// CONFIG
// -----------------------------------------------------------------------------
#define NMAX 50  // Max map dimension (the spec says at least 15x15, but let's allow up to 50x50)
int N = 15;     // Actual dimension read from file (or fixed if you prefer)


// -----------------------------------------------------------------------------
// GLOBALS
// -----------------------------------------------------------------------------
char mapData[NMAX][NMAX];   // The map: '0'=obstacle, '1'=soil, '2'=start, '3'=mission
int visitedSoil[NMAX][NMAX]; // Keep track of visited cells (for coverage or display)
int startR, startC;          // The rover's start location

// Orientation: 0=up, 1=right, 2=down, 3=left
// Movement vectors for forward/back
int dr[4] = {-1, 0, 1,  0};
int dc[4] = { 0, 1, 0, -1};

// For printing/fuel stats
int totalFuel = 0;

// -----------------------------------------------------------------------------
// DATA STRUCTURES
// -----------------------------------------------------------------------------

// A state in our search = (row, col, dir)
typedef struct {
    int r, c;
    int dir;
    int cost;  // for priority queue
} State;

// Parent info for reconstructing path
typedef struct {
    int pr, pc, pdir; // parent state
    char moveType;    // for debugging or animation steps
} ParentInfo;

// A simple min-heap/priority queue for State
// For an advanced project, use a better data structure if you prefer.
typedef struct {
    State arr[NMAX*NMAX*4];
    int size;
} MinHeap;

// -----------------------------------------------------------------------------
// UTILITY FUNCTIONS
// -----------------------------------------------------------------------------

// Compare states by cost
int cmpState(State a, State b){
    return (a.cost < b.cost) ? -1 : (a.cost > b.cost ? 1 : 0);
}

// Swap two states in the heap
void swap(State *a, State *b){
    State tmp = *a; 
    *a = *b; 
    *b = tmp;
}

// Push a state into the min-heap
void pushHeap(MinHeap *h, State s){
    h->arr[++h->size] = s;
    int idx = h->size;
    // bubble up
    while(idx > 1 && cmpState(h->arr[idx], h->arr[idx/2]) < 0){
        swap(&h->arr[idx], &h->arr[idx/2]);
        idx /= 2;
    }
}

// Pop the top (smallest) state from the min-heap
State popHeap(MinHeap *h){
    State ret = h->arr[1];
    // Move last to root
    h->arr[1] = h->arr[h->size--];
    // bubble down
    int idx = 1;
    while(1){
        int left = 2*idx, right = 2*idx+1;
        int smallest = idx;
        if(left <= h->size && cmpState(h->arr[left], h->arr[smallest]) < 0) {
            smallest = left;
        }
        if(right <= h->size && cmpState(h->arr[right], h->arr[smallest]) < 0){
            smallest = right;
        }
        if(smallest == idx) break;
        swap(&h->arr[idx], &h->arr[smallest]);
        idx = smallest;
    }
    return ret;
}

// Check if min-heap is empty
int heapEmpty(MinHeap *h){
    return (h->size == 0);
}

// Check if cell in bounds and not an obstacle
int validCell(int r, int c){
    if(r < 0 || r >= N || c < 0 || c >= N) return 0;
    return (mapData[r][c] != '0');
}

// Clear screen and print map with visited status and stats
void printMap(int rVehicle, int cVehicle){
#ifdef _WIN32
    system("cls");
#else
    system("clear");
#endif

    // Print the map
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(i == rVehicle && j == cVehicle){
                // Print the rover with some symbol
                printf("R ");
            }
            else {
                printf("%c ", mapData[i][j]);
            }
        }
        printf("\n");
    }
    // Stats
    printf("\nTotal fuel used: %d\n", totalFuel);
}

// -----------------------------------------------------------------------------
// STATE-SPACE SEARCH (D' BFS or uniform-cost search) to find minimal fuel path
// -----------------------------------------------------------------------------

/*
   We do a uniform-cost (D') BFS in the state space of (r, c, dir).
   We store dist[r][c][dir] = minimal cost to get there.
   We allow these moves from (r, c, dir):
     1) Move forward 1 cell  (cost=1) -> (r+dr[dir], c+dc[dir], dir)
     2) Move backward 1 cell (cost=1) -> (r-dr[dir], c-dc[dir], dir)
     3) Turn left            (cost=3) -> orientation changes, same (r,c)
     4) Turn right           (cost=3) -> orientation changes, same (r,c)
     5) Shift left           (cost=3) -> move sideways left, same dir
     6) Shift right          (cost=3) -> move sideways right, same dir

   We continue until we reach (targetR, targetC) in *any* orientation.
   Then we reconstruct the path by using a parent[] array.
*/

int distCost[NMAX][NMAX][4];   // track best cost so far
ParentInfo parentInfo[NMAX][NMAX][4];  // for path reconstruction

// For convenience, define an inline helper for shifting:
void shiftRC(int r, int c, int dir, int leftOrRight, int *rOut, int *cOut) {
    // leftOrRight: -1 => shift left, +1 => shift right
    // If facing up (dir=0), shifting left => (r, c-1), shifting right => (r, c+1)
    // If facing right (dir=1), shifting left => (r-1, c), shifting right => (r+1, c)
    // If facing down (dir=2), shifting left => (r, c+1), shifting right => (r, c-1)
    // If facing left (dir=3), shifting left => (r+1, c), shifting right => (r-1, c)
    switch(dir){
        case 0: *rOut = r;       *cOut = c + leftOrRight * (-1); break; // up
        case 1: *rOut = r + leftOrRight * (-1); *cOut = c;       break; // right
        case 2: *rOut = r;       *cOut = c + leftOrRight;        break; // down
        case 3: *rOut = r + leftOrRight;        *cOut = c;       break; // left
    }
}

// Run uniform-cost search from (sr, sc, sdir) to (tr, tc, anyDir).
// Returns the minimal cost, or -1 if unreachable.
// Reconstruct the path in the array 'steps' if needed for animation.
int findPath(int sr, int sc, int sdir, int tr, int tc) {
    // Initialize dist[][][]
    for(int r=0; r<N; r++){
        for(int c=0; c<N; c++){
            for(int d=0; d<4; d++){
                distCost[r][c][d] = INT_MAX;
                parentInfo[r][c][d].pr = -1;
                parentInfo[r][c][d].pc = -1;
                parentInfo[r][c][d].pdir = -1;
                parentInfo[r][c][d].moveType = '?';
            }
        }
    }
    distCost[sr][sc][sdir] = 0;

    MinHeap pq; 
    pq.size = 0;
    pushHeap(&pq, (State){sr, sc, sdir, 0});

    while(!heapEmpty(&pq)){
        State st = popHeap(&pq);
        int r = st.r, c = st.c, d = st.dir, costSoFar = st.cost;

        // If this cost is stale, skip
        if(costSoFar > distCost[r][c][d]) continue;

        // Goal check: if we've reached the target cell in ANY orientation
        if(r == tr && c == tc){
            return costSoFar;
        }

        // Expand neighbors:
        // 1) Forward
        {
            int rr = r + dr[d], cc = c + dc[d];
            if(validCell(rr, cc)){
                int ncost = costSoFar + 1;  // forward cost = 1
                if(ncost < distCost[rr][cc][d]){
                    distCost[rr][cc][d] = ncost;
                    parentInfo[rr][cc][d] = (ParentInfo){r, c, d, 'F'};
                    pushHeap(&pq, (State){rr, cc, d, ncost});
                }
            }
        }
        // 2) Backward
        {
            int rr = r - dr[d], cc = c - dc[d];
            if(validCell(rr, cc)){
                int ncost = costSoFar + 1; // backward cost = 1
                if(ncost < distCost[rr][cc][d]){
                    distCost[rr][cc][d] = ncost;
                    parentInfo[rr][cc][d] = (ParentInfo){r, c, d, 'B'};
                    pushHeap(&pq, (State){rr, cc, d, ncost});
                }
            }
        }
        // 3) Turn left
        {
            int nd = (d + 3) % 4; // left turn
            int ncost = costSoFar + 3; // turning cost=3
            if(ncost < distCost[r][c][nd]){
                distCost[r][c][nd] = ncost;
                parentInfo[r][c][nd] = (ParentInfo){r, c, d, 'L'};
                pushHeap(&pq, (State){r, c, nd, ncost});
            }
        }
        // 4) Turn right
        {
            int nd = (d + 1) % 4;
            int ncost = costSoFar + 3;
            if(ncost < distCost[r][c][nd]){
                distCost[r][c][nd] = ncost;
                parentInfo[r][c][nd] = (ParentInfo){r, c, d, 'R'};
                pushHeap(&pq, (State){r, c, nd, ncost});
            }
        }
        // 5) Shift left
        {
            int rr, cc;
            shiftRC(r, c, d, -1, &rr, &cc); // leftOrRight=-1 => shift left
            if(validCell(rr, cc)){
                int ncost = costSoFar + 3;
                if(ncost < distCost[rr][cc][d]){
                    distCost[rr][cc][d] = ncost;
                    parentInfo[rr][cc][d] = (ParentInfo){r, c, d, 'S'}; // 'S' can denote "shift-left" or you'll store more detail if you want
                    pushHeap(&pq, (State){rr, cc, d, ncost});
                }
            }
        }
        // 6) Shift right
        {
            int rr, cc;
            shiftRC(r, c, d, +1, &rr, &cc);
            if(validCell(rr, cc)){
                int ncost = costSoFar + 3;
                if(ncost < distCost[rr][cc][d]){
                    distCost[rr][cc][d] = ncost;
                    parentInfo[rr][cc][d] = (ParentInfo){r, c, d, 's'}; 
                    pushHeap(&pq, (State){rr, cc, d, ncost});
                }
            }
        }
    }

    // If we exhaust the queue, target is unreachable
    return -1;
}

// Reconstruct the path from parentInfo[][][] once we know which (r,c,dir) solved it.
// Then “replay” the moves step by step to accumulate fuel cost and animate.
void reconstructAndMove(int targetR, int targetC) {
    // We want the orientation at target that gave minimal dist
    int bestDir=-1, bestCost=INT_MAX;
    for(int d=0; d<4; d++){
        if(distCost[targetR][targetC][d] < bestCost){
            bestCost = distCost[targetR][targetC][d];
            bestDir = d;
        }
    }
    if(bestCost == INT_MAX){
        // unreachable
        return;
    }
    // Build the path in reverse
    int pathLen = 0;
    static int PR[10000], PC[10000], PD[10000];
    int cr=targetR, cc=targetC, cd=bestDir;
    while(cd != -1){
        PR[pathLen] = cr;
        PC[pathLen] = cc;
        PD[pathLen] = cd;
        ParentInfo p = parentInfo[cr][cc][cd];
        int nr = p.pr, nc = p.pc, nd = p.pdir;
        cd = nd; cr = nr; cc = nc;
        if(cd < 0) break;
        pathLen++;
    }
    // Replay from start of pathLen down to 0
    for(int i=pathLen-1; i >= 0; i--){
        int rr = PR[i];
        int cc = PC[i];
        // figure out cost difference from distCost of the next step
        // but simpler is: we already know bestCost, or we can recalc from parent’s move
        // For a nicer animation: 
        //   print the map with R at (rr, cc), 
        //   increment totalFuel based on the move we took to get here.
        // Actually, we can deduce the move cost from parent’s moveType:
        //   (But we didn’t store the cost of each transition, so we re-check it.)
        // Simpler approach: we just track distCost differences.
        if(i < pathLen-1){
            int rPrev = PR[i+1], cPrev = PC[i+1], dPrev = PD[i+1];
            int costDiff = distCost[rr][cc][PD[i]] - distCost[rPrev][cPrev][dPrev];
            totalFuel += (costDiff > 0 ? costDiff : 0);
        }

        // “Mark” the path (optional). If cell was '1' or '3', we can replace with '*'.
        // But do not overwrite '2' if it’s the original start. Your choice.
        if(mapData[rr][cc] == '1') mapData[rr][cc] = '*';
        if(mapData[rr][cc] == '3') mapData[rr][cc] = '*';

        // Animate
        printMap(rr, cc);
        SLEEP(200);
    }
}

// -----------------------------------------------------------------------------
// MAIN
// -----------------------------------------------------------------------------

int main(){
    // 1) Read the map file
    //    For simplicity, we assume the file has N lines of length N (or set N=15).
    //    Adjust as needed if your input is bigger or you want a dynamic N, etc.
    const char *filename = "input.txt";
    FILE *fp = fopen(filename, "r");
    if(!fp){
        printf("Cannot open %s\n", filename);
        return 1;
    }
    // If you prefer to read the first line for N, do so. Otherwise, fix N=15 or 20, etc.
    N = 15; // or read it from file if you want
    // read lines
    int foundStart=0;
    for(int i=0; i<N; i++){
        fscanf(fp, "%s", mapData[i]);
        if((int)strlen(mapData[i]) < N){
            printf("Map line %d is too short!\n", i);
            fclose(fp);
            return 1;
        }
        for(int j=0; j<N; j++){
            if(mapData[i][j] == '2'){
                startR = i;
                startC = j;
                foundStart=1;
            }
        }
    }
    fclose(fp);
    if(!foundStart){
        printf("No start cell ('2') found!\n");
        return 1;
    }

    // 2) Gather mission spots
    //    Let’s store them in an array for sequential visiting or nearest-first, etc.
    typedef struct { int r, c; } Node;
    Node missions[100];
    int missionCount=0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            visitedSoil[i][j] = 0;  // init visited array
            if(mapData[i][j] == '3'){
                missions[missionCount].r = i;
                missions[missionCount].c = j;
                missionCount++;
            }
        }
    }

    // Mark the start cell as visited (for coverage stats if you like)
    visitedSoil[startR][startC] = 1;
    totalFuel = 0;

    // 3) If we have mission spots, do a “visit them all” step.
    //    Simplest approach: just visit them in the order found. 
    //    A more advanced approach: pick the nearest mission each time.
    int currR = startR, currC = startC, currDir = 0; // face “up” at start
    for(int m=0; m<missionCount; m++){
        int tr = missions[m].r;
        int tc = missions[m].c;
        // Find path from (currR, currC, currDir) to (tr, tc)
        int cost = findPath(currR, currC, currDir, tr, tc);
        if(cost < 0){
            printf("Mission spot (%d,%d) unreachable!\n", tr, tc);
            // you could continue to next mission or break
            continue;
        }
        // Reconstruct & move
        reconstructAndMove(tr, tc);

        // We ended at (tr, tc) in some orientation. Let’s figure out which one:
        int bestDir=-1, bestCost=INT_MAX;
        for(int d=0; d<4; d++){
            if(distCost[tr][tc][d] < bestCost){
                bestCost = distCost[tr][tc][d];
                bestDir = d;
            }
        }
        // Update current
        currR = tr; 
        currC = tc;
        currDir = bestDir;
    }

    // 4) If no missions, or after finishing missions, do a coverage pass:
    //    We can do a simple BFS over all reachable '1' cells, or we can do
    //    state-based BFS again. For brevity, let's just do a naive BFS ignoring orientation,
    //    marking all reachable cells. (You can expand this to orientation-based coverage.)
    //    We show a minimal example:
    {
        // We’ll do a standard BFS in grid space (no orientation).
        int used[NMAX][NMAX];
        memset(used, 0, sizeof(used));
        Node queue[NMAX*NMAX];
        int front=0, back=0;
        queue[back++] = (Node){currR, currC};
        used[currR][currC] = 1;

        while(front < back){
            Node u = queue[front++];
            for(int i=0; i<4; i++){
                int rr = u.r + dr[i];
                int cc = u.c + dc[i];
                if(rr<0||rr>=N||cc<0||cc>=N) continue;
                if(!used[rr][cc] && mapData[rr][cc] != '0'){
                    used[rr][cc] = 1;
                    // “Pretend” we move there in 1 cost if you want, or do a path with orientation BFS, etc.
                    // For demonstration, we'll say cost=1 for each BFS step:
                    totalFuel += 1;
                    if(mapData[rr][cc] == '1') mapData[rr][cc] = '*'; 
                    printMap(rr, cc);
                    SLEEP(50);

                    queue[back++] = (Node){rr, cc};
                }
            }
        }
    }

    // 5) Done
    printf("All missions processed. Coverage BFS done.\n");
    printf("Final total fuel used: %d\n", totalFuel);

    return 0;
}
Leave a Comment