#48 老鼠走迷宮 (mouse maze)

在大學的資料結構的課程裡，大約在教過 Stack, Queue 和 List 這些基本的資料結構之後會有一個老鼠走迷宮的作業．這份作業說難不難，說簡單也沒那麼簡單，對一個正在學習資料結構的學生來說，花個一兩個晚上來寫這份作業是很正常的．如果寫程式正是你的工作，而且你以前沒念過資料結構的話，不妨試著做做看這份作業．

老鼠走迷宮的內容是，要隨機產生一個矩陣，矩陣的大小最好由使用者輸入設定的．然後在矩陣裡的每個位置也會隨機產生三種不同的地形，例如平地，河流與高山．你可以再設計其他不同的地形，老鼠在每一個地形上走動時會花費不同的體力，例如平地是 1 ，河流是 2，而老鼠是無法穿越高山．老鼠的出發點是矩陣的左上角，也就是 (0,0) 的位置, 然後終點在右下角，也就是 (n,m) 的位置，n,m 代表的是矩陣的兩個邊長．

你所要寫的程式是讓使用者輸入矩陣的大小，然後為矩陣的每一個格子隨機產生地形，接著老鼠從出發點開始移動，看看老鼠是否可以走到終點．因為地形中會有高山，所以老鼠不一定都會有一條路可以走到終點．然而，老鼠能走的路也可能不只一條能到終點，你可以試著找出一條就行了．

整個題目的重點在於兩個地方．第一，移動的方向要定出一套規則，第二，要能夠記錄走過的路跡．移動方向的規則可以用最簡單的方式來實行，除了在邊邊與角落以外的格子，每個格子都可以有八種移動方向，上，下，左，右，左上，左下，右上，右下．每到達一個格子時，就可以依照固定的順序來移動到下一個格子，如果在下一個格子都沒有路走或是每個方向都試過了，那就回到上一個格子．因此，路跡的記錄是很重要的，因為需要回到上一個格子．

以下我提供十多年前寫的版本

	static void Main(string[] args)
	{
	//Declare number of row and column of the maze
	int maze_row , maze_col ;
	Console.Write ("Input the number of row of the maze : ") ;
	maze_row = int.Parse ( Console.ReadLine () ) ;
	Console.Write ("Input the number of column of the maze : ") ;
	maze_col = int.Parse ( Console.ReadLine () ) ;
	maze_col = maze_col + 2 ;
	int[,] maze = new int[maze_row,maze_col]; //maze array
	int[,] mark = new int[maze_row,maze_col]; //mark array
	//Generate all landforms of the maze, 9:Start & End, 1:Road, 2:Hill, 3:River
	Random ra1 = new Random () ;
	int i,j ;
	for ( i = 0 ; i < maze_row ; i++ )
	{
	for ( j = 0 ; j < maze_col ; j++ )
	{
	if ( j==0 || j==maze_col-1 )
	maze[i,j] = 2 ;
	else
	maze[i,j] = ra1.Next(1,4) ;
	}
	}
	maze[0,0] = 9 ;
	maze[maze_row-1,maze_col-1] = 9 ;
	for ( i=0 ; i <maze_row ; i++ )
	{
	for (j=0; j<maze_col ; j++ )
	{
	mark[i,j] = 0 ;
	}
	}
	for (i=0 ; i <maze_row; i++)
	{
	mark[i,0] = 1;
	mark[i,maze_col-1] = 1 ;
	}
	mark[maze_row-1,maze_col-1] = 0 ;
	//Populate the maze to screen
	Console.WriteLine ("--------9:Start & End, 1:Road, 2:Hill, 3:River--------") ;
	Console.Write (" ") ;
	for ( i=1 ; i<maze_col-1; i++ )
	{
	Console.Write (" {0}", i ) ;
	}
	Console.WriteLine () ;
	Console.Write ("--") ;
	for ( i=1 ; i<maze_col; i++ )
	{
	Console.Write ("--") ;
	}
	Console.WriteLine () ;
	for (i=0 ; i < maze_row; i++)
	{
	for (j=0;j < maze_col ;j++)
	{
	if ( j == 0)
	Console.Write ("{0}|", i+1 ) ;
	if ( maze[i,j] == 0 )
	Console.Write (" " + " " );
	else
	Console.Write (" "+ maze[i,j].ToString () );
	}
	Console.WriteLine () ;
	}
	Console.WriteLine ("\n") ;
	//Declare possible direction
	Direction[] dir1 = new Direction[8] ;
	dir1[3].vert = -1 ;
	dir1[3].horiz = 0 ; //north
	dir1[2].vert = -1 ;
	dir1[2].horiz = 1 ; //northeast
	dir1[0].vert = 0 ;
	dir1[0].horiz = 1 ; //east
	dir1[1].vert = 1 ;
	dir1[1].horiz = 1 ; //southeast
	dir1[4].vert = 1 ;
	dir1[4].horiz = 0 ; //south
	dir1[5].vert = 1 ;
	dir1[5].horiz = -1 ; //southwest
	dir1[6].vert = 0 ;
	dir1[6].horiz = -1 ; //west
	dir1[7].vert = -1 ;
	dir1[7].horiz = -1 ; //norhtwest
	//declare the stack
	Stack stack1 = new Stack ( maze_row * maze_col ) ;
	Path position = new Path () ;
	position.row = 0 ;
	position.col = 0 ;
	position.dir = 0 ;
	stack1.Push (position) ;
	int cur_row =0 , cur_col=0 , next_row =0 , next_col =0 , dir ;
	bool found = false ,flag1 = false ;
	int cost = 0 , rat_power = 0 ;
	int show_row=0 , show_col=0 ;
	Console.WriteLine ("The path is : ") ;
	#region "outloop"
	while ( !found )
	{
	//Console.WriteLine ("Stack count : {0}", stack1.Count ) ;
	if ( stack1.Count == 0 )
	break ;
	if (flag1)
	{
	cur_row = next_row ;
	cur_col = next_col ;
	dir = 0 ;
	}
	else
	{
	mark[cur_row,cur_col] = 1 ;
	Path temp_pos = (Path) stack1.Pop () ;
	//Console.WriteLine ("Stack count : {0}", stack1.Count ) ;
	cur_row = temp_pos.row ;
	cur_col = temp_pos.col ;
	dir = temp_pos.dir ;
	if (cur_row==0 && cur_col==0)
	cost = 0;
	else
	cost -= maze[cur_row,cur_col];
	if (maze[cur_row,cur_col]==3)
	rat_power -- ;
	}
	#region "innerloop"
	while ( dir < 8 && !found )
	{
	next_row = cur_row + dir1[dir].vert ;
	next_col = cur_col + dir1[dir].horiz ;
	if ( next_row ==maze_row-1 && next_col==maze_col-1 )
	{
	cost += maze[cur_row,cur_col] ;
	found = true ;
	break ;
	}
	if ( next_row < 0 || next_row >= maze_row || next_col<=0 || next_col>=maze_col-1 )
	{
	dir ++ ;
	continue ;
	}
	if ( maze[next_row,next_col]==1 && mark[next_row,next_col]==0 )
	{
	rat_power = 0 ;
	mark[cur_row,cur_col]=1;
	Path cur_pos = new Path () ;
	cur_pos.row = cur_row ;
	cur_pos.col = cur_col ;
	cur_pos.dir = dir ++ ;
	stack1.Push ( cur_pos );
	cost += maze[cur_row,cur_col] ;
	flag1 = true ;
	break ;
	}
	else if ( maze[next_row,next_col]==3 && mark[next_row,next_col]==0 )
	{
	rat_power ++ ;
	if (rat_power >= 4 )
	{
	mark[cur_row,cur_col]=1;
	dir++ ;
	flag1 = false ;
	rat_power -- ;
	Console.Write ("*") ;
	}
	else
	{
	mark[cur_row,cur_col]=1;
	Path cur_pos = new Path () ;
	cur_pos.row = cur_row ;
	cur_pos.col = cur_col ;
	cur_pos.dir = dir ++ ;
	stack1.Push ( cur_pos );
	cost += maze[cur_row,cur_col] ;
	flag1 = true ;
	break ;
	}
	}
	else
	{
	dir++ ;
	flag1 = false ;
	}
	}
	#endregion
	show_row = cur_row +1 ;
	show_col = cur_col ;
	if ( !found)
	{
	if ( cur_row == 0 && cur_col == 0 )
	Console.Write ("[0,0] ->" ) ;
	else
	Console.Write ("["+ show_row.ToString() + "," + show_col.ToString () +"] --> " );
	}
	else
	{
	Console.WriteLine ("["+ show_row.ToString() + "," + show_col.ToString () +"] " );
	}
	}
	#endregion
	if ( found )
	{
	Console.WriteLine ("\nThere is a path") ;
	Console.WriteLine ("\nThe cost is : {0}", cost-9) ;
	}
	else
	{
	Console.WriteLine ("\nThere is no path") ;
	}
	Console.ReadLine () ; //pause for interaction
	}

view raw mousemaze.cs hosted with ❤ by GitHub

如果你順利寫完之後，還有一個延伸題目給你繼續挑戰，那就是如果有多條可以走的路跡時，列出最省力的路跡．這延伸題目就不是那麼簡單了，未來再來寫篇文章來討論．