Untitled
unknown
plain_text
3 months ago
17 kB
2
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
int N = 15; // Map dimension read from file
// -----------------------------------------------------------------------------
// GLOBALS
// -----------------------------------------------------------------------------
char mapData[NMAX][NMAX]; // The map: '0'=obstacle, '1'=soil, '2'=start, '3'=mission
int visitedSoil[NMAX][NMAX];
int startR, startC; // The vehicle's anchor (top-left corner in its orientation)
int totalFuel = 0; // Accumulates fuel usage
// Orientation: 0=up, 1=right, 2=down, 3=left
int dr[4] = {-1, 0, 1, 0};
int dc[4] = { 0, 1, 0, -1};
// -----------------------------------------------------------------------------
// VEHICLE SHAPE (2×3 or 3×2)
// -----------------------------------------------------------------------------
#define NUM_VEHICLE_CELLS 6
// shapeOffsets[orientation][which_of_6_cells][0/1]
int shapeOffsets[4][NUM_VEHICLE_CELLS][2] = {
// orientation=0 (up)
{
{0,0},{0,1},{0,2},
{1,0},{1,1},{1,2}
},
// orientation=1 (right)
{
{0,0},{1,0},{2,0},
{0,1},{1,1},{2,1}
},
// orientation=2 (down)
{
{0,0},{0,1},{0,2},
{1,0},{1,1},{1,2}
},
// orientation=3 (left)
{
{0,0},{1,0},{2,0},
{0,1},{1,1},{2,1}
}
};
// Check if all 6 cells for the 2×3 shape are valid (not '0', in-bounds)
int validVehiclePosition(int r, int c, int dir) {
int k;
for(k=0; k<NUM_VEHICLE_CELLS; k++){
int rr = r + shapeOffsets[dir][k][0];
int cc = c + shapeOffsets[dir][k][1];
if(rr < 0 || rr >= N || cc < 0 || cc >= N) {
return 0;
}
if(mapData[rr][cc] == '0') {
return 0;
}
}
return 1;
}
// -----------------------------------------------------------------------------
// STRUCTS
// -----------------------------------------------------------------------------
typedef struct {
int r, c;
int dir;
int cost;
} State;
typedef struct {
int pr, pc, pdir;
char moveType;
} ParentInfo;
typedef struct {
State arr[NMAX*NMAX*4];
int size;
} MinHeap;
// -----------------------------------------------------------------------------
// MIN-HEAP (priority queue) UTILS
// -----------------------------------------------------------------------------
int cmpState(State a, State b){
if(a.cost < b.cost) return -1;
if(a.cost > b.cost) return 1;
return 0;
}
void swap(State *a, State *b){
State tmp = *a;
*a = *b;
*b = tmp;
}
void pushHeap(MinHeap *h, State s){
h->arr[++h->size] = s;
int idx = h->size;
while(idx > 1 && cmpState(h->arr[idx], h->arr[idx/2]) < 0){
swap(&h->arr[idx], &h->arr[idx/2]);
idx /= 2;
}
}
State popHeap(MinHeap *h){
State ret = h->arr[1];
h->arr[1] = h->arr[h->size--];
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;
}
int heapEmpty(MinHeap *h){
return (h->size == 0);
}
// -----------------------------------------------------------------------------
// PRINT MAP + VEHICLE
// -----------------------------------------------------------------------------
void printMap(int rVehicle, int cVehicle, int dirVehicle){
#ifdef _WIN32
system("cls");
#else
system("clear");
#endif
static char display[NMAX][NMAX];
memcpy(display, mapData, sizeof(mapData));
int k;
for(k=0; k<NUM_VEHICLE_CELLS; k++){
int rr = rVehicle + shapeOffsets[dirVehicle][k][0];
int cc = cVehicle + shapeOffsets[dirVehicle][k][1];
display[rr][cc] = 'R';
}
int i,j;
for(i=0; i<N; i++){
for(j=0; j<N; j++){
printf("%c ", display[i][j]);
}
printf("\n");
}
printf("\nTotal fuel used: %d\n", totalFuel);
}
// -----------------------------------------------------------------------------
// SHIFT HELPER
// -----------------------------------------------------------------------------
void shiftRC(int r, int c, int dir, int leftOrRight, int *rOut, int *cOut) {
// leftOrRight: -1 => shift left, +1 => shift right
switch(dir){
case 0: // up
*rOut = r;
*cOut = c + (leftOrRight * -1);
break;
case 1: // right
*rOut = r + (leftOrRight * -1);
*cOut = c;
break;
case 2: // down
*rOut = r;
*cOut = c + leftOrRight;
break;
case 3: // left
*rOut = r + leftOrRight;
*cOut = c;
break;
}
}
// -----------------------------------------------------------------------------
// UNIFORM-COST SEARCH (FOR MISSIONS)
// -----------------------------------------------------------------------------
int distCost[NMAX][NMAX][4];
ParentInfo parentInfo[NMAX][NMAX][4];
int findPath(int sr, int sc, int sdir, int tr, int tc){
int r,c,d;
for(r=0; r<N; r++){
for(c=0; c<N; c++){
for(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);
r = st.r;
c = st.c;
d = st.dir;
int costSoFar = st.cost;
// Skip stale
if(costSoFar > distCost[r][c][d]) continue;
// Goal check
if(r == tr && c == tc){
return costSoFar;
}
// Expand neighbors:
// 1) Forward
{
int rr = r + dr[d];
int cc = c + dc[d];
if(validVehiclePosition(rr, cc, d)){
int ncost = costSoFar + 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];
int cc = c - dc[d];
if(validVehiclePosition(rr, cc, d)){
int ncost = costSoFar + 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;
int ncost = costSoFar + 3;
if(validVehiclePosition(r, c, nd)){
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(validVehiclePosition(r, c, nd)){
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);
int ncost = costSoFar + 3;
if(validVehiclePosition(rr, cc, d)){
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});
}
}
}
// 6) Shift right
{
int rr, cc;
shiftRC(r, c, d, +1, &rr, &cc);
int ncost = costSoFar + 3;
if(validVehiclePosition(rr, cc, d)){
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});
}
}
}
}
return -1; // unreachable
}
// -----------------------------------------------------------------------------
// RECONSTRUCT PATH + ANIMATE
// -----------------------------------------------------------------------------
void reconstructAndMove(int targetR, int targetC){
// Find best orientation
int bestDir = -1, bestCost = INT_MAX;
int d;
for(d=0; d<4; d++){
if(distCost[targetR][targetC][d] < bestCost){
bestCost = distCost[targetR][targetC][d];
bestDir = d;
}
}
if(bestCost == INT_MAX){
return; // unreachable
}
static int PR[10000], PC[10000], PD[10000];
int pathLen = 0;
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++;
}
int i;
for(i = pathLen - 1; i >= 0; i--){
int rr = PR[i];
int cc = PC[i];
int dd = PD[i];
// Increase totalFuel by cost difference
if(i < pathLen - 1){
int rPrev = PR[i+1];
int cPrev = PC[i+1];
int dPrev = PD[i+1];
int costDiff = distCost[rr][cc][dd] - distCost[rPrev][cPrev][dPrev];
if(costDiff > 0) totalFuel += costDiff;
}
// Mark path if desired
int k;
for(k=0; k<NUM_VEHICLE_CELLS; k++){
int rCell = rr + shapeOffsets[dd][k][0];
int cCell = cc + shapeOffsets[dd][k][1];
if(mapData[rCell][cCell] == '1') mapData[rCell][cCell] = '*';
if(mapData[rCell][cCell] == '3') mapData[rCell][cCell] = '*';
}
// Animate
printMap(rr, cc, dd);
SLEEP(200);
}
}
// -----------------------------------------------------------------------------
// SHAPE-AWARE COVERAGE BFS
// -----------------------------------------------------------------------------
void coverageBFS(int startR, int startC, int startDir) {
// For coverage BFS, we store visited states in usedCover[r][c][d].
static int usedCover[NMAX][NMAX][4];
memset(usedCover, 0, sizeof(usedCover));
typedef struct {
int r, c, d;
} QState;
QState queue[NMAX*NMAX*4];
int front = 0, back = 0;
queue[back++] = (QState){ startR, startC, startDir };
usedCover[startR][startC][startDir] = 1;
while(front < back){
QState u = queue[front++];
int r = u.r, c = u.c, d = u.d;
// Mark the 6 occupied cells
int k;
for(k=0; k<NUM_VEHICLE_CELLS; k++){
int rr = r + shapeOffsets[d][k][0];
int cc = c + shapeOffsets[d][k][1];
if(mapData[rr][cc] == '1') mapData[rr][cc] = '*';
if(mapData[rr][cc] == '3') mapData[rr][cc] = '*';
}
// Show the current vehicle position
printMap(r, c, d);
SLEEP(100);
// We'll do the same 6 moves with costs.
// Only add cost once if we haven't visited the neighbor state.
// 1) Forward
{
int rr = r + dr[d];
int cc = c + dc[d];
if(validVehiclePosition(rr, cc, d) && !usedCover[rr][cc][d]){
usedCover[rr][cc][d] = 1;
totalFuel += 1; // forward cost
queue[back++] = (QState){ rr, cc, d };
printMap(rr, cc, d);
SLEEP(100);
}
}
// 2) Backward
{
int rr = r - dr[d];
int cc = c - dc[d];
if(validVehiclePosition(rr, cc, d) && !usedCover[rr][cc][d]){
usedCover[rr][cc][d] = 1;
totalFuel += 1; // backward cost
queue[back++] = (QState){ rr, cc, d };
printMap(rr, cc, d);
SLEEP(100);
}
}
// 3) Turn left
{
int nd = (d + 3) % 4;
if(validVehiclePosition(r, c, nd) && !usedCover[r][c][nd]){
usedCover[r][c][nd] = 1;
totalFuel += 3;
queue[back++] = (QState){ r, c, nd };
printMap(r, c, nd);
SLEEP(100);
}
}
// 4) Turn right
{
int nd = (d + 1) % 4;
if(validVehiclePosition(r, c, nd) && !usedCover[r][c][nd]){
usedCover[r][c][nd] = 1;
totalFuel += 3;
queue[back++] = (QState){ r, c, nd };
printMap(r, c, nd);
SLEEP(100);
}
}
// 5) Shift left
{
int rr, cc;
shiftRC(r, c, d, -1, &rr, &cc);
if(validVehiclePosition(rr, cc, d) && !usedCover[rr][cc][d]){
usedCover[rr][cc][d] = 1;
totalFuel += 3;
queue[back++] = (QState){ rr, cc, d };
printMap(rr, cc, d);
SLEEP(100);
}
}
// 6) Shift right
{
int rr, cc;
shiftRC(r, c, d, +1, &rr, &cc);
if(validVehiclePosition(rr, cc, d) && !usedCover[rr][cc][d]){
usedCover[rr][cc][d] = 1;
totalFuel += 3;
queue[back++] = (QState){ rr, cc, d };
printMap(rr, cc, d);
SLEEP(100);
}
}
}
}
// -----------------------------------------------------------------------------
// MAIN
// -----------------------------------------------------------------------------
int main(){
// 1) Read map
const char *filename = "input.txt";
FILE *fp = fopen(filename, "r");
if(!fp){
printf("Cannot open %s\n", filename);
return 1;
}
N = 15; // or read from file
int i;
int foundStart = 0;
for(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;
}
}
fclose(fp);
// 2) Find start cell '2'
int j;
for(i=0; i<N && !foundStart; i++){
for(j=0; j<N && !foundStart; j++){
if(mapData[i][j] == '2'){
startR = i;
startC = j;
foundStart = 1;
}
}
}
if(!foundStart){
printf("No start cell ('2') found!\n");
return 1;
}
// 3) Gather missions
typedef struct {int r,c;} Node;
Node missions[100];
int missionCount = 0;
for(i=0; i<N; i++){
for(j=0; j<N; j++){
visitedSoil[i][j] = 0;
if(mapData[i][j] == '3'){
missions[missionCount].r = i;
missions[missionCount].c = j;
missionCount++;
}
}
}
// initial orientation = 0 (up)
int currR = startR;
int currC = startC;
int currDir = 0;
totalFuel = 0;
// 4) Visit each mission
for(i=0; i<missionCount; i++){
int tr = missions[i].r;
int tc = missions[i].c;
int cost = findPath(currR, currC, currDir, tr, tc);
if(cost < 0){
printf("Mission spot (%d, %d) unreachable!\n", tr, tc);
continue;
}
reconstructAndMove(tr, tc);
// figure out final orientation used
int d, bestDir=-1, bestCost=INT_MAX;
for(d=0; d<4; d++){
if(distCost[tr][tc][d] < bestCost){
bestCost = distCost[tr][tc][d];
bestDir = d;
}
}
currR = tr;
currC = tc;
currDir = bestDir;
}
// 5) Coverage BFS from final (r,c,dir)
coverageBFS(currR, currC, currDir);
// 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