|
5啊哈币
char A[64][64]= {"..###","#....","#.#.#","#.#.#","#.#.."};//迷宫,A,R,C这里预设,实际请改成输入
int M[64][64] = {0}, //标记走过的点
R = 5, C = 5;
//判断点(x,y)是否可达
bool pass(int x, int y)
{
return x>=0 && x<=R && y>=0 && y<=C
&& A[x][y]=='.' && !M[x][y];
}
//广度搜索
int steps()
{
struct{ int x, y, depth;}Queue[256], t; //队列
int front = 0, rear = 0, //头尾指标
di[4][2] = {{1,0},{0,-1},{-1,0},{0,1}}; //方向数组
int i, new_x, new_y;
Queue[rear].x = 0; //初始点入队
Queue[rear].y = 0;
Queue[rear++].depth = 1;
M[0][0] = 1; //标记该店
while(front != rear)
{
t = Queue[front++]; //出队
for(i=0; i<4; i++) //遍历每个方向
{
new_x = t.x+di[i][0]; //产生新的坐标
new_y = t.y+di[i][1];
if(pass( new_x, new_y)) //若可达
{
if(new_x==R-1 && new_y==C-1)return t.depth+1; //结束条件
//入队
Queue[rear].x = new_x;
Queue[rear].y = new_y;
Queue[rear++].depth = t.depth+1;
M[new_x][new_y] = 1; //同样标记入队的点
}
}
}
return -1; //无法走到终点,返回-1
}
int main()
{
printf("%d", steps());
}
|
|