#include <string.h>
#include "graphics.h"
#define GRID_SIZE_X 10
#define GRID_SIZE_Y 10
#define ROBOT 'R'
#define HOME_X 9
#define HOME_Y 2
#define MARKER_X 7
#define MARKER_Y 7
#define ROBOT_X 6
#define ROBOT_Y 5
#define MAX_N 105
int g_father[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
int last_dir[MAX_N][MAX_N];
int dir[MAX_N*MAX_N];
char g_has_visited[MAX_N][MAX_N]; //vis[x][y]表示xy点是否遍历过
int Queue[MAX_N*MAX_N]; //用Q来模拟队列 给定两个下标 front和rear 那么入队则是Q[rear++]=u 出队是u=Q[front++]
int coordinate[MAX_N*MAX_N];
const int squareSize = 50;
const int windowSize = 600;
// Define the grid elements
const char EMPTY = ' ';
const char BLOCK = '#';
const char MARKER = '*';
const char HOME = 'H';
// Define robot directions
typedef enum { WEST , EAST, NORTH, SOUTH }Direction;
// Define the robot struct
typedef struct {
int x;
int y;
Direction direction;
char carryingMarker;
}Robot;
void drawStep(int homeX, int homeY)
{
background();
setColour(pink);
homeX = homeX*squareSize;
homeY = homeY*squareSize;
fillRect(homeX, homeY, squareSize, squareSize);
}
void drawMarker(int x,int y)
{
background();
setColour(gray);
x = x*squareSize;
y = y*squareSize;
fillRect(x, y, squareSize, squareSize);
}
void drawBlocks(int x,int y)
{
background();
setColour(black);
x = x*squareSize;
y = y*squareSize;
fillRect(x, y, squareSize, squareSize);
}
void drawEmpty(int x,int y)
{
foreground();
setColour(white);
x = x*squareSize;
y = y*squareSize;
fillRect(x, y, squareSize, squareSize);
}
// Function to initialize the grid
void initializeGrid(char grid[][GRID_SIZE_Y]) {
// Initialize the grid with empty spaces
for (int i = 0; i < GRID_SIZE_X; ++i) {
for (int j = 0; j < GRID_SIZE_X; ++j) {
grid[i][j] = EMPTY;
}
}
// Place blocks, markers, and home square
grid[8][8] = BLOCK;
grid[9][5] = BLOCK;
grid[8][5] = BLOCK;
grid[7][5] = BLOCK;
grid[6][7] = BLOCK;
grid[8][7] = BLOCK;
grid[7][8] = BLOCK;
grid[7][8] = BLOCK;
grid[2][2] = BLOCK;
grid[3][3] = BLOCK;
grid[4][4] = BLOCK;
grid[5][5] = BLOCK;
grid[6][6] = BLOCK;
grid[MARKER_X][MARKER_Y] = MARKER;
grid[HOME_X][HOME_Y] = HOME;
}
// Function to display the grid
void displayGrid(const char grid[][GRID_SIZE_X]) {
setWindowSize(windowSize, windowSize);
background(); // Must draw on the background layer.
int x;
int y;
for (x=0; x<GRID_SIZE_X; x++)
{
for (y=0; y<GRID_SIZE_X; y++)
{
drawRect(x*squareSize, y*squareSize,
squareSize, squareSize);
}
}
}
void draw_north(int x, int y)
{
int x_coords[] = {x, x+50, x+25};
int y_coords[] = {y+50, y+50, y};
fillPolygon(3, x_coords, y_coords);
}
void draw_east(int x, int y)
{
int x_coords[] = {x, x, x+50};
int y_coords[] = {y, y+50, y+25};
fillPolygon(3, x_coords, y_coords);
}
void draw_south(int x, int y)
{
int x_coords[] = {x, x+50, x+25};
int y_coords[] = {y, y, y+50};
fillPolygon(3, x_coords, y_coords);
}
void draw_west(int x, int y)
{
int x_coords[] = {x+50, x+50, x};
int y_coords[] = {y, y+50, y+25};
fillPolygon(3, x_coords, y_coords);
}
// Function to drop a marker
void dropMarker(Robot *robot, char grid[][GRID_SIZE_X]) {
if (!robot->carryingMarker) {
return; // Robot is not carrying a marker
}
grid[robot->x][robot->y] = MARKER;
robot->carryingMarker = 0;
//drawRobot(robot.x, robot.y, (int)robot.direction);
}
void drawRobot(int x, int y, int direction)
{
foreground();
clear();
setColour(green);
x = x*squareSize;
y = y*squareSize;
switch (direction)
{
case NORTH: draw_north(x, y); break;
case EAST: draw_east(x, y); break;
case SOUTH: draw_south(x, y); break;
case WEST: draw_west(x, y); break;
}
}
void drawRobotWithBg(int x, int y, int direction)
{
foreground();
clear();
setColour(gray);
x = x*squareSize;
y = y*squareSize;
fillRect(x, y, squareSize, squareSize);
setColour(green);
switch (direction)
{
case NORTH: draw_north(x, y); break;
case EAST: draw_east(x, y); break;
case SOUTH: draw_south(x, y); break;
case WEST: draw_west(x, y); break;
}
}
void drawHome(int homeX, int homeY)
{
background();
setColour(blue);
homeX = homeX*squareSize;
homeY = homeY*squareSize;
fillRect(homeX, homeY, squareSize, squareSize);
}
void drawShort(int homeX, int homeY)
{
background();
setColour(orange);
homeX = homeX*squareSize;
homeY = homeY*squareSize;
fillRect(homeX, homeY, squareSize, squareSize);
}
void forward(Robot *robot, char grid[][GRID_SIZE_X]) {
// Calculate the next position based on the direction
int nextX = robot->x;
int nextY = robot->y;
if (robot->direction == NORTH) {
--nextX;
} else if (robot->direction == SOUTH) {
++nextX;
} else if (robot->direction == EAST) {
++nextY;
} else if (robot->direction == WEST) {
--nextY;
}
// Check if the next position is valid
if (nextX >= 0 && nextX < GRID_SIZE_X && nextY >= 0 && nextY < GRID_SIZE_X && grid[nextX][nextY] != BLOCK) {
// Move the robot
grid[robot->x][robot->y] = EMPTY;
robot->x = nextX;
robot->y = nextY;
grid[robot->x][robot->y] = ROBOT;
}
drawRobot(robot->x, robot->y, robot->direction);
}
char markersLeft(char grid[][GRID_SIZE_X]) {
for (int i = 0; i < GRID_SIZE_X; ++i) {
for (int j = 0; j < GRID_SIZE_X; ++j) {
if (grid[i][j] == MARKER) {
return 1;
}
}
}
return 0;
}
void turn_left(Robot *robot) {
if (robot->direction == NORTH) {
robot->direction = WEST;
} else if (robot->direction == SOUTH) {
robot->direction = EAST;
} else if (robot->direction == EAST) {
robot->direction = NORTH;
} else if (robot->direction == WEST) {
robot->direction = SOUTH;
}
drawRobot(robot->x, robot->y, robot->direction);
}
void turn_right(Robot *robot) {
if (robot->direction == NORTH) {
robot->direction = EAST;
} else if (robot->direction == SOUTH) {
robot->direction = WEST;
} else if (robot->direction == EAST) {
robot->direction = SOUTH;
} else if (robot->direction == WEST) {
robot->direction = NORTH;
}
drawRobot(robot->x, robot->y, robot->direction);
}
// Function to pick up a marker
void pickUpMarker(Robot *robot, char grid[][GRID_SIZE_Y]) {
if (grid[robot->x][robot->y] == MARKER) {
robot->carryingMarker = 1;
grid[robot->x][robot->y] = EMPTY;
}
}
void findAndCollectMarkers(Robot *robot, char grid[][GRID_SIZE_X]) {
while (markersLeft(grid)) {
int initialX = robot->x;
int initialY = robot->y;
Direction initialDirection = robot->direction;
// Use the "right hand rule" to navigate
if (robot->direction == NORTH) {
if (grid[robot->x][robot->y + 1] != BLOCK) {
turn_right(robot);
} else if (grid[robot->x - 1][robot->y] != BLOCK) {
forward(robot, grid);
} else {
turn_left(robot);
}
} else if (robot->direction == SOUTH) {
if (grid[robot->x][robot->y - 1] != BLOCK) {
turn_right(robot);
} else if (grid[robot->x + 1][robot->y] != BLOCK) {
forward(robot, grid);
} else {
turn_left(robot);
}
} else if (robot->direction == EAST) {
if (grid[robot->x + 1][robot->y] != BLOCK) {
turn_right(robot);
} else if (grid[robo
