Untitled

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef _WIN32
  #include <windows.h>  // For Sleep on Windows
  #define SLEEP(ms) Sleep(ms)
#else
  #include <unistd.h>   // For usleep on Linux/macOS
  #define SLEEP(ms) usleep((ms)*1000)
#endif

#define N 15

/*
 * Map legend (example):
 * '0' = obstacle
 * '1' = free/soil cell
 * '2' = start position
 * 'M' or '3' = mission spot(s) you must visit
 */

// Global map
char mapData[N][N];
int visited[N][N];
int startX, startY;

// For BFS or pathfinding
typedef struct {
    int r, c;
} Node;

// Directions: up, right, down, left
int dr[4] = {-1, 0, 1, 0};
int dc[4] = { 0, 1, 0,-1};

// Some “stats” to display
int fuelCost   = 0;  // each move can cost 1 fuel
int cellsScanned = 0; // how many distinct soil cells have been scanned

// Utility: clear screen and print map + stats
void printInterface() {
    // Clear screen
    #ifdef _WIN32
        system("cls");
    #else
        system("clear");
    #endif

    // Print map
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            printf("%c ", mapData[i][j]);
        }
        printf("\n");
    }
    // Print “control panel”
    printf("\nFuel Used : %d\n", fuelCost);
    printf("Cells Scanned : %d\n", cellsScanned);
    printf("-----------------------\n");
}

// Check if (r, c) is inside the grid and not a '0'
int validCell(int r, int c) {
    if(r < 0 || r >= N || c < 0 || c >= N) return 0;
    if(mapData[r][c] == '0') return 0;
    return 1;
}

// BFS to find a path from (sr, sc) to (tr, tc).
// Returns path length, and fills path[] with the route in reverse order.
// If no path, returns -1.
int bfsPath(int sr, int sc, int tr, int tc, Node path[], int *pathLen) {
    if(sr == tr && sc == tc){
        *pathLen = 0; 
        return 0; // Already there
    }

    // Visited array for BFS
    int used[N][N];
    memset(used, 0, sizeof(used));

    // Parent array for reconstructing path
    Node parent[N][N];
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            parent[i][j].r = -1;
            parent[i][j].c = -1;
        }
    }

    // BFS queue
    Node queue[N*N];
    int front=0, back=0;

    queue[back++] = (Node){sr, sc};
    used[sr][sc] = 1;

    // BFS
    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(validCell(rr, cc) && !used[rr][cc]){
                used[rr][cc] = 1;
                parent[rr][cc] = u;
                queue[back++] = (Node){rr, cc};
                if(rr == tr && cc == tc) {
                    // Found it! Reconstruct path
                    int len=0;
                    Node cur = (Node){tr, tc};
                    while(cur.r != -1) {
                        path[len++] = cur;
                        cur = parent[cur.r][cur.c];
                    }
                    *pathLen = len;
                    return len;
                }
            }
        }
    }
    // Not found
    return -1;
}

// Move step-by-step along the path
// Mark each step with '*' in the map (except final mission spot if you want it intact)
void moveAlongPath(Node path[], int pathLen) {
    // The path[] is in reverse order (end -> start).
    // We want to traverse from start to end:
    for(int i = pathLen - 1; i >= 0; i--) {
        int r = path[i].r;
        int c = path[i].c;

        // “Move” to (r, c)
        // If it's not the starting cell and not a mission spot, mark visited
        if(mapData[r][c] != '2' && mapData[r][c] != 'M' && mapData[r][c] != '3') {
            mapData[r][c] = '*';
        }

        // Use 1 fuel
        fuelCost++;

        // If we are stepping onto a new soil (or mission spot), increment scanned
        // (You could refine logic if you only want to count '1' or 'M' once.)
        if(!visited[r][c]) {
            visited[r][c] = 1;
            cellsScanned++;
        }

        // Show the step
        printInterface();

        // Delay a bit so user can see the movement
        SLEEP(300);
    }
}

// Find all mission spots (M or '3') and store them in an array
// Returns how many mission spots found
int findMissions(Node missions[]) {
    int count = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(mapData[i][j] == 'M' || mapData[i][j] == '3'){
                missions[count++] = (Node){i, j};
            }
        }
    }
    return count;
}

// Euclidean or Manhattan distance (for “closest” mission)
int manhattanDist(int r1, int c1, int r2, int c2){
    return abs(r1 - r2) + abs(c1 - c2);
}

// Simple function to do “coverage” BFS (or “lawnmower”) after missions
// so you can show scanning of all soil cells. This is just a simple BFS from start.
void coverageBFS(int sr, int sc) {
    // Standard BFS
    int used[N][N];
    memset(used, 0, sizeof(used));
    Node queue[N*N];
    int front=0, back=0;

    queue[back++] = (Node){sr, sc};
    used[sr][sc] = 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(validCell(rr, cc) && !used[rr][cc]){
                used[rr][cc] = 1;

                // Step onto (rr, cc)
                // Mark path if not 'M', '3', or '2'
                if(mapData[rr][cc] != 'M' && mapData[rr][cc] != '3' && mapData[rr][cc] != '2') {
                    mapData[rr][cc] = '*';
                }
                fuelCost++;
                if(!visited[rr][cc]) {
                    visited[rr][cc] = 1;
                    cellsScanned++;
                }
                printInterface();
                SLEEP(200);

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

// Read map from file
void readMap(const char *filename){
    FILE *fp = fopen(filename, "r");
    if(!fp){
        printf("Cannot open %s\n", filename);
        exit(1);
    }

    int foundStart = 0;
    for(int i=0; i<N; i++){
        fscanf(fp, "%s", mapData[i]);
        if(strlen(mapData[i]) < N){
            printf("Each row in the map file must have %d chars.\n", N);
            fclose(fp);
            exit(1);
        }
        for(int j=0; j<N; j++){
            if(mapData[i][j] == '2'){
                startX = i;
                startY = j;
                foundStart = 1;
            }
        }
    }
    fclose(fp);

    if(!foundStart){
        printf("No start cell ('2') found in the map!\n");
        exit(1);
    }
}

int main() {
    const char *filename = "input.txt";

    // 1) Read map and init
    readMap(filename);
    memset(visited, 0, sizeof(visited));

    // Mark the start as visited
    visited[startX][startY] = 1;
    cellsScanned = 1; // We start on '2'
    fuelCost = 0;

    // 2) Print initial
    printInterface();

    // 3) Find all mission spots
    Node missions[100];
    int missionCount = findMissions(missions);

    // Current robot position
    int currR = startX;
    int currC = startY;

    // 4) While missions remain, pick the closest one (by Manhattan distance),
    //    BFS to it, remove it from the list.
    while(missionCount > 0) {
        // Find the nearest mission
        int bestIdx = 0;
        int bestDist = 999999;
        for(int i=0; i<missionCount; i++){
            int dist = manhattanDist(currR, currC, missions[i].r, missions[i].c);
            if(dist < bestDist){
                bestDist = dist;
                bestIdx = i;
            }
        }
        // BFS from (currR, currC) to that mission
        Node path[500];
        int pathLen=0;
        int rTarg = missions[bestIdx].r;
        int cTarg = missions[bestIdx].c;
        int found = bfsPath(currR, currC, rTarg, cTarg, path, &pathLen);
        if(found == -1){
            // No path to that mission; skip it or break
            printf("No path to mission at (%d,%d). Skipping.\n", rTarg, cTarg);
        } else {
            // Follow the path
            moveAlongPath(path, pathLen);
            // We end on that mission cell
            currR = rTarg;
            currC = cTarg;
        }

        // Remove this mission from the array (swap with last, missionCount--)
        missionCount--;
        missions[bestIdx] = missions[missionCount];
    }

    // 5) After all missions are visited, do a coverage BFS from the final position
    coverageBFS(currR, currC);

    // 6) Final output
    printf("All missions visited (or attempted).\n");
    printf("Coverage BFS done.\n");
    printInterface();  // show final state
    printf("Program finished.\n");

    return 0;
}