这本来不是要作为答案的，但实际上已经演变成了一个答案。老实说，我认为从Java开始并转向C是一个坏主意，因为这两种语言确实没有什么相似之处，而且您不会帮上忙，因为如果您依赖于Java的任何功能，在移植它时都会遇到严重的问题。有C没有（即大多数）
也就是说，我将草拟一些算法C的东西。
typedef
struct Node
{
int x, y;
// x and y are array indices
}
Node;
typedef
struct Path
{
int maxlen, head;
Node * path;
// maxlen is size of path, head is the index of the current node
// path is the pointer to the node array
}
Path;
int node_compare(Node * n1, Node * n2); // returns true if nodes are equal, else false
void path_setup(Path * p, Node * n); // allocates Path.path and sets first node
void path_embiggen(Path * p); // use realloc to make path bigger in case it fills up
int path_toosmall(Path * p); // returns true if the path needs to be reallocated to add more nodes
Node * path_head(Path * p); // returns the head node of the path
void path_push(Path * p, Node * n); // pushes a new head node onto the path
void path_pop(Path * p); // pops a node from path
您可能将迷宫格式更改为邻接列表之类的东西。您可以将每个节点存储为掩码，详细说明可以从该节点访问的节点。
const int // these constants indicate which directions of travel are possible from a node
N = (1 << 0), // travel NORTH from node is possible
S = (1 << 1), // travel SOUTH from node is possible
E = (1 << 2), // travel EAST from node is possible
W = (1 << 3), // travel WEST from node is possible
NUM_DIRECTIONS = 4; // number of directions (might not be 4. no reason it has to be)
const int
START = (1 << 4), // starting node
FINISH = (1 << 5); // finishing node
const int
MAZE_X = 4, // maze dimensions
MAZE_Y = 4;
int maze[MAZE_X][MAZE_Y] =
{
{E, S|E|W, S|E|W, S|W },
{S|FINISH, N|S, N|START, N|S },
{N|S, N|E, S|E|W, N|S|W },
{N|E, E|W, N|W, N }
};
Node start = {1, 2}; // position of start node
Node finish = {1, 0}; // position of end node
我的迷宫与您的迷宫不同：两种格式彼此之间并非完全一对一地映射。例如，您的格式允许更精细的移动，但是我的格式允许单向路径。
请注意，您的格式明确指定了墙的位置。按照我的格式，墙在概念上位于无法通行的任何地方。我创建的迷宫有3个水平墙和5个垂直墙（并且也是封闭的，即有连续的墙围绕着整个迷宫）
为了进行遍历，我将使用深度优先搜索。您可以通过多种方式将标志映射到方向，例如以下所示。由于无论如何都要遍历每个对象，因此访问时间是无关紧要的，因此仅使用数组而不是某种更快的关联容器就足够了。
// map directions to array offsets
// format is [flag], [x offset], [y offset]
int mappings[][] =
{
{N, -1, 0},
{S, 1, 0},
{E, 0, 1},
{W, 0, -1}
}
最后，您的搜索。您可以迭代或递归实现。我的示例使用递归。
int search_for_path(int ** maze, char ** visited, Path * path)
{
Node * head = path_head(path);
Node temp;
int i;
if (node_compare(head, &finish)) return 1; // found finish
if (visited[head->x][head->y]) return 0; // don't traverse again, that's pointless
visited[head->x][head->y] = 1;
if (path_toosmall(path)) path_embiggen(path);
for (i = 0; i < NUM_DIRECTIONS; ++i)
{
if (maze[head->x][head->y] & mappings[i][0]) // path in this direction
{
temp = {head->x + mappings[i][1], head->y + mappings[i][2]};
path_push(path, &temp);
if (search_for_path(maze, visited, path)) return 1; // something found end
path_pop(path);
}
}
return 0; // unable to find path from any unvisited neighbor
}
// we already have the maze
// int maze[MAZE_X][MAZE_Y] = {...};
// make a visited list, set to all 0 (unvisited)
int visited[MAZE_X][MAZE_Y] =
{
{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}
};
// setup the path
Path p;
path_setup(&p, &start);
if (search_for_path(maze, visited, &path))
{
// succeeded, path contains the list of nodes containing coordinates from start to end
}
else
{
// maze was impossible
}
值得注意的是，因为我在编辑框中都写了这些，所以我还没有测试过。第一次尝试可能无法正常工作，可能需要花些时间。例如，除非在全局范围内声明了开始和结束，否则会有一些问题。最好将目标节点传递给搜索功能，而不要使用全局变量。
602392714
清零编程群