Untitled
unknown
plain_text
a year ago
17 kB
8
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;
}
Editor is loading...
Leave a Comment