迷宫探索

/*迷宫由 N W S E 组成  踩到N向上走一格 踩到W 向左走一格 踩到S向下走一格 踩到E 向右走一格
输入迷宫行数  列数  不大于10 机器人初始列数(注意 这个列数是从1开始数的) 判断能否走出迷宫。能走出输出步数
多组输入 遇 0 0 0 结束输入
例
输入
4 6 5
NNNNSN
NNNSWN
NNSWNN
NSWNNN
3 5 2
NSNNNN
NSWNNN
NENNNN
0 0 0
输出
7
no

*/
/*分析:程序输入 n m c 即行 列 机器人位置:passed[ii][jj](ii = 1;jj = c;)采取net[11][11]记录输入的方向,passed[11][11]记录机器人走过的路,先初始化为0,走过改为1,
        初始步子count = 1;成功flag = 0用作while条件;while循环用模拟走路的方法,
		1. 1 == passed[ii][jj],机器人位置 ii jj走过,
		flag = 1;
		2. 如果'N' == net[ii][jj]向上走一格,1 == ii则走出了,否则passed[ii][jj] = 1;//改变记录数组 1表示走过
		ii = ii - 1; //向上走一格,count ++;   //步子加一
		3. 如果'S' == net[ii][jj]向下走一格,n == ii则走出了,否则passed[ii][jj] = 1;//改变记录数组 1表示走过
		ii = ii + 1; //向上走一格,count ++;   //步子加一
		4.如果'W' == net[ii][jj]向左走一格,1 == jj则走出了,否则passed[ii][jj] = 1;//改变记录数组 1表示走过
		jj = jj - 1; //向上走一格,count ++;   //步子加一
		5.如果'E' == net[ii][jj]向右走一格,m == jj则走出了,否则passed[ii][jj] = 1;//改变记录数组 1表示走过
		jj = jj+1; //向上走一格,count ++;   //步子加一
		以上已遍历完毕,判断if(1 == flag)//记录数组中都是一 ,都走完了,没法走出
		
		从新输入图scanf("%d %d %d",&n,&m,&c);
*/
#include <stdio.h>

int main()
{
	char net[11][11];							//记录方向
	int passed[11][11];							//passed[i][j] = 1表示该点已走过
	int n,m,c;                                  //n行m列的迷宫 机器人从c列开始走
	int i,j,ii,jj,flag;
	int count;
	scanf("%d %d %d",&n,&m,&c);
	while(0 != n && 0 != m && 0 != c)
	{
		count = 1;
		flag = 0;
		
		for(i=1;i<=n;++i)//输入
			scanf("%s",&net[i][1]);

		for(i=1;i<=n;++i)//记录走过的二维数组初始化0表示未走过
			for(j=1;j<=m;++j)
				passed[i][j] = 0;

		ii = 1;
		jj = c;

		while(1)//一直循环 加break做退出循环条件
		{
			if(1 == passed[ii][jj])//机器人位置 ii jj走过
			{
				flag = 1;
				break;
			}
			if('N' == net[ii][jj])
			{
				if(1 == ii)						//已到达最上端还要往上走,
				{
					printf("%d\n",count);      
					break;
				}
				else
				{
					passed[ii][jj] = 1;//改变记录数组 1表示走过
					ii = ii - 1; //向上走一格
					count ++;   //步子加一
				}
			}//end if('N' == net[ii][jj])
			else if('S' == net[ii][jj])
			{
				if(n == ii)						//已到达最下端还要往下走,
				{
					printf("%d\n",count);
					break;
				}
				else
				{
					passed[ii][jj] = 1;
					ii = ii + 1;
					count ++;
				}
			}//end else if('S' == net[ii][jj])
			else if('W' == net[ii][jj])
			{
				if(1 == jj)						//已到达最左端还要往左走,
				{
					printf("%d\n",count);
					break;
				}
				else
				{
					passed[ii][jj] = 1;
					jj = jj - 1;
					count ++;
				}
			}//end else if('W' == net[ii][jj])
			else if('E' == net[ii][jj])
			{
				if(m == jj)						//已到达最右端还要往右走,
				{
					printf("%d\n",count);
					break;
				}
				else
				{
					passed[ii][jj] = 1;
					jj = jj + 1;
					count ++;
				}
			}//end else if('E' == net[ii][jj])
		}//end while(true)
		
		if(1 == flag)//记录数组中都是一 ,都走完了
			printf("no\n");
		
		scanf("%d %d %d",&n,&m,&c);//寻找失败 从新输入
	}//end while
	return 0;
}

上一篇:Linux 格式化分区及挂载文件系统


下一篇:Android开发教程 - 使用Data Binding(五)数据绑定