Untitled
#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