1344 - 算法3-3：迷宫

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 32 MB

有一个 10 x 10 的迷宫，起点是‘S’，终点是‘E’，墙是‘#’，道路是空格。一个机器人从起点走到终点。当机器人走到一个通道块，前面已经没有路可走时，它会转向到当前面向的右手方向继续走。如果机器人能够过，则留下足迹‘*’，如果走不通，则留下标记‘!’。

下面给出书中的算法，请你模拟机器人的走法输出最终的状态。

图：迷宫算法

题目输入

一个 10 x 10 的二维字符数组。

题目输出

机器人走过的路径状态。

输入/输出样例

输入格式

##########
#S #   # #
#  #   # #
#    ##  #
# ###    #
#   #    #
# #   #  #
# ### ## #
##      E#
##########

输出格式

##########
#**#!!!# #
# *#!!!# #
#**!!##  #
#*###    #
#***#    #
# #***#  #
# ###*## #
##   ****#
##########

C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char arr[10][11];
int getPath(int start,int end);
int Pass(int pos);
int nextpos(int curpos);
int main()
{
  int i,j;
  int start,end;
  for(i=0;i<10;i++)
  {
      for(j=0;j<10;j++)
        arr[i][j]=getchar();
      getchar();
  }
   for(i=0;i<10;i++)
     for(j=0;j<10;j++)
     {
         if(arr[i][j]=='S')
            start=i*10+j;
         else if(arr[i][j]=='E')
            end=i*10+j;
     }
  if(getPath(start,end))
  {
      for(i=0;i<10;i++)
      {
          for(j=0;j<10;j++)
           putchar(arr[i][j]);
          printf("\n");
      }
  }
  else
  {
      printf("ERROR!");
  }
  return 0;
}

int getPath(int start,int end)
{
    int S[100],top=-1;
    int curpos;
    int x,y;
    curpos=start;
    do
    {
            x=curpos/10;
            y=curpos%10;
            arr[x][y]='*';
            if(curpos==end)
              return 1;
            S[++top]=curpos;
            while(!(curpos=nextpos(curpos))&&top!=-1)
            {
                curpos=S[top--];
                x=curpos/10;
                y=curpos%10;
                arr[x][y]='!';
                curpos=S[top];
            }
    }while(top!=-1);
    return 0;

}

int Pass(int curpos)
{
    int x,y;
    x=curpos/10;
    y=curpos%10;
    if(arr[x][y]==' '||arr[x][y]=='S'||arr[x][y]=='E')
      return 1;
    else
      return 0;
}
int nextpos(int curpos)
{
    int i,j,newpos;
    i=curpos/10;
    j=curpos%10;
    if(j+1<10)
    {
        newpos=curpos+1;
        if(Pass(newpos))
        {
            return newpos;
        }

    }
    if(i+1<10)
    {
        newpos=curpos+10;
        if(Pass(newpos))
          return newpos;
    }
    if(j-1>=0)
    {
        newpos=curpos-1;
        if(Pass(newpos))
          return newpos;
    }
    if(i-1>=0)
    {
        newpos=curpos-10;
        if(Pass(newpos))
          return newpos;
    }
      return 0;
}

C++解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STACK_INIT_SIZE 100		// 存储空间初始分配量
#define STACKINCREMENT 10		// 存储空间分配增量
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW 0				// 栈分配溢出

typedef struct{
	int r, c;		// 以行号和列号作为“坐标位置”类型
}PosType;

typedef struct{
	int ord;		// 通道块在路径上的序号
	PosType seat;	// 通道块在迷宫中的“坐标位置”
	int di;			// 从此通道块走向下一通道块的“方向”
}SElemType;			// 定义堆栈元素的类型

typedef struct {
	SElemType * base;			// 在栈构造之前和销毁之后，base的值为NULL
	SElemType * top;			// 栈顶指针
	int stacksize;				// 当前已分配的存储空间，以元素为单位
}SqStack;

typedef struct{
	char arr[10][11];
}MazeType;	// 定义迷宫类型（二维字符数组）

Status InitStack(SqStack &S){
	// 构造一个空栈
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base) exit(OVERFLOW);		// 存储分配失败
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}// InitStack

Status GetTop(SqStack S, SElemType &e){
	// 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR
	if(S.top == S.base) return ERROR;
	e = *(S.top-1);
	return OK;
}// GetTop

Status Push(SqStack &S, SElemType e){
	// 插入元素 e 为新的栈顶元素
	if(S.top - S.base >= S.stacksize){	//栈满，追加存储空间
		S.base = (SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) exit(OVERFLOW);	// 存储分配失败
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
} // Push

Status Pop(SqStack &S, SElemType &e){
	// 若栈不为空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR
	if(S.top == S.base) return ERROR;
	e = * --S.top;
	return OK;
} // Pop

Status StackEmpty(SqStack S){
	// 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE
	return S.top == S.base;
} // StackEmpty

void ClearStack(SqStack &S){
	// 将栈 S 清空
	S.top = S.base;
} // ClearStack

void DestroyStack(SqStack &S){
	// 销毁整个栈
	while(S.top != S.base){	// 释放栈中元素的空间
		free(--S.top);
	}
	S.top = S.base = NULL;
} // DestroyStack

Status Pass(MazeType MyMaze, PosType CurPos) {
	if (MyMaze.arr[CurPos.r][CurPos.c]==' ' || MyMaze.arr[CurPos.r][CurPos.c]=='S' || MyMaze.arr[CurPos.r][CurPos.c]=='E')
		return 1; // 如果当前位置是可以通过，返回1
	else
		return 0; // 其它情况返回0
}

void FootPrint(MazeType &MyMaze, PosType CurPos) {
	MyMaze.arr[CurPos.r][CurPos.c] = '*';
}

void MarkPrint(MazeType &MyMaze, PosType CurPos) {
	MyMaze.arr[CurPos.r][CurPos.c] = '!';
}

PosType NextPos(PosType CurPos, int Dir) {
	PosType ReturnPos;
	switch (Dir) {
	case 1:
		ReturnPos.r = CurPos.r;
		ReturnPos.c = CurPos.c + 1;
		break;
	case 2:
		ReturnPos.r = CurPos.r + 1;
		ReturnPos.c = CurPos.c;
		break;
	case 3:
		ReturnPos.r = CurPos.r;
		ReturnPos.c = CurPos.c - 1;
		break;
	case 4:
		ReturnPos.r = CurPos.r - 1;
		ReturnPos.c = CurPos.c;
		break;
	}
	return ReturnPos;
}

Status MazePath(MazeType &maze, PosType start, PosType end) {
	// 算法3.3
	// 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中
	// （从栈底到栈顶），并返回TRUE；否则返回FALSE
	SqStack S;
	PosType curpos;
	int curstep;
	SElemType e;

	InitStack(S);
	curpos = start; // 设定"当前位置"为"入口位置"
	curstep = 1; // 探索第一步
	do {
		if (Pass(maze, curpos)) { // 当前位置可通过，即是未曾走到过的通道块
			FootPrint(maze, curpos); // 留下足迹
			e.di = 1;
			e.ord = curstep;
			e.seat = curpos;
			Push(S, e); // 加入路径
			if (curpos.r == end.r && curpos.c == end.c)
				return (TRUE); // 到达终点（出口）
			curpos = NextPos(curpos, 1); // 下一位置是当前位置的东邻
			curstep++; // 探索下一步
		} else { // 当前位置不能通过
			if (!StackEmpty(S)) {
				Pop(S, e);
				while (e.di == 4 && !StackEmpty(S)) {
					MarkPrint(maze, e.seat);
					Pop(S, e); // 留下不能通过的标记，并退回一步
				} // while
				if (e.di < 4) {
					e.di++;
					Push(S, e); // 换下一个方向探索
					curpos = NextPos(e.seat, e.di); // 当前位置设为新方向的相邻块
				} // if
			} // if
		} // else
	} while (!StackEmpty(S));
	return FALSE;
} // MazePath

int main(){

	int i, j;
	PosType start, end;						// 起点终点坐标
	MazeType maze;							// 迷宫
	memset(maze.arr, 0, sizeof(maze.arr));	// 将字符串设置为空
	for(i=0;i<10;i++){						// 读取迷宫数据
		gets(maze.arr[i]);
		for(j=0;j<10;j++){
			if(maze.arr[i][j] == 'S'){		// 获得起点坐标
				start.r = i;
				start.c = j;
			}else if(maze.arr[i][j] == 'E'){// 获得终点坐标
				end.r = i;
				end.c = j;
			}
		}
	}

	MazePath(maze, start, end);				// 移动
	for(i=0;i<10;i++){						// 输出状态
		puts(maze.arr[i]);
	}

	return 0;
}

Java解答

import java.io.*;

class queen {
	public int Func(char m[][],int f[][],int x,int y)
	{
		int t;
		f[y][x]=0;
		if(m[y][x]=='E')
		{
			m[y][x]='*';
			return -1;
		}
		m[y][x]='!';
		if(x<9&&m[y][x+1]!='#'&&f[y][x+1]==1)
		{
			m[y][x]='*';
			if((t=Func(m,f,x+1,y))==1)
			{
				m[y][x]='!';
			}
			else if(t==-1)
				return -1;
		}
		if(y<9&&m[y+1][x]!='#'&&f[y+1][x]==1)
		{
			m[y][x]='*';
			if((t=Func(m,f,x,y+1))==1)
			{
				m[y][x]='!';
			}
			else if(t==-1)
				return -1;
		}
		if(x>0&&m[y][x-1]!='#'&&f[y][x-1]==1)
		{
			m[y][x]='*';
			if((t=Func(m,f,x-1,y))==1)
			{
				m[y][x]='!';
			}
			else if(t==-1)
				return -1;
		}
		if(y>0&&m[y-1][x]!='#'&&f[y-1][x]==1)
		{
			m[y][x]='*';
			if((t=Func(m,f,x,y-1))==1)
			{
				m[y][x]='!';
			}
			else if(t==-1)
				return -1;
		}
		if(m[y][x]=='!')
			return 1;
		return 0;
	}
}
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
		char m[][]=new char[10][10],t;
		int f[][]=new int[10][10];
		queen q=new queen();
		int px=0,py=0;
		String a;
		for(int i=0;i<10;i++)
		{
			a=cin.readLine();
			for(int j=0;j<10;j++)
			{
				f[i][j]=1;
				m[i][j]=a.charAt(j);
				if(m[i][j]=='S')
				{
					px=i;py=j;
				}
			}
		}
		q.Func(m,f,px,py);
		for(int i=0;i<10;i++)
		{
			for(int j=0;j<10;j++)
				System.out.print(m[i][j]);
			System.out.print("\n");
		}
	}
}

上一题下一题提示代码讨论统计