fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  5. #define directions 8
  6.  
  7. class Step
  8. {
  9. 	public:
  10. 		Step();		
  11. 		Step(int a,int b);
  12. 		void get(Step current, int* possibleSteps, int number);		
  13. 		int x; 
  14. 		int y; 	
  15. };
  16.  
  17. Step::Step() {
  18.     x=0;
  19.     y=0;
  20. }
  21.  
  22. Step::Step(int a, int b) {
  23.     x=a;
  24.     y=b;
  25. }
  26.  
  27. int count(int* possibleSteps) {					//傳入紀錄可走方向的一維陣列
  28.     int c, i;									//變數c用來接出路數量(初始值0)、變數i為8方向計數器
  29.     for(c = 0, i = 0; i < directions; i++)		//檢查八個方向
  30. 	 if(possibleSteps[i]) {						//如果這個方向有值(值為1或0而已)
  31.      	   c++;									//出路數就+1
  32.     	   }									//結束小if迴圈
  33.     return c;									//回傳出路數量
  34. }												//count函式結束
  35.  
  36. void Step::get(Step current, int* possibleSteps, int number) {		//傳入現在座標，已經記錄好可走方向的一維陣列，第幾條出路(最少為1)
  37. 	const int idir[8]={-2,-1,1,2, 2, 1,-1,-2};  //能走的8個方向i值的變化
  38. 	const int jdir[8]={ 1, 2,2,1,-1,-2,-2,-1};  //能走的8個方向j值的變化
  39.     int c=0, i=0;	
  40.     for(c = 0, i = 0; i < directions; i++) if(possibleSteps[i]) {
  41.         c++;
  42.         if(c == number) {
  43.             break;
  44.         }
  45.     }
  46. 	this->x=current.x+idir[i];
  47. 	this->y=current.y+jdir[i];
  48. }
  49.  
  50. void travel(int n)
  51. {
  52. 	const int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1}, 	  
  53.                       {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; 	  //八個方向的移動
  54. 	int **board;  												  //將來要輸出在螢幕上的棋盤
  55. 	board=new int*[n];  										  //nXn陣列
  56. 	for(int x=0;x<n;x++)
  57. 	{
  58. 		board[x]=new int[n];
  59. 	}
  60. 	for(int x=0;x<n;x++)  							//將board初始化
  61. 	{
  62. 		for(int y=0;y<n;y++)
  63. 			board[x][y]=0;
  64. 	}
  65. 	board[0][0]=1;									//起點為(0,0)
  66.  
  67. 	Step current=Step(0,0);							//現今騎士的座標
  68. 	int st;											//代表步數計數器*/
  69. 	for(st = 2; st <n*n+1; st++){					//走滿步(格)數就算完成*/ 
  70. 		int possibleSteps[directions]={0};			//一維陣列，8方向*/
  71. 		int k;										//變數k為8方向計數器
  72.     	for(k = 0; k < directions; k++)				//run8個方向的for迴圈
  73.     	{					
  74.         	Step s = Step(current.x + dirs[k][0], current.y + dirs[k][1]);	//s代表往方向k後的座標位置     	
  75. 			if( s.x > -1 && s.x < n &&s.y > -1 && s.y < n)//決定下個位置可不可以走
  76. 			{
  77.             	if(!board[s.x][s.y]) 					//而且這個位置沒有被佔據(值大於1即為被占據)
  78.             	{						
  79.             	possibleSteps[k] = 1;				//我們就把這個方向設定為1(值為1或0。1可以走，0不可以走)        	 	
  80. 				}
  81. 			}										//if迴圈結束     	 	
  82.     	}											//for迴圈結束	
  83.  
  84.         int c = count(possibleSteps);				//c代表現在這個位置有幾個出路 
  85.  
  86. 		if(c == 0){									/*沒有出路即為死路，跳出迴圈*/ 
  87. 			break;
  88. 		}
  89.  
  90. 		if(c == 1) {								/*如果只有一條出路，下一步只有一個可能*/
  91.           current.get(current, possibleSteps, 1);
  92.       }	
  93.  
  94.         else {
  95. 			const int tdirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; 											
  96. 			int minPossibleSteps[directions] = {0};  
  97.     		Step s1=Step();
  98. 			s1.get(current, possibleSteps, 1);
  99.  
  100.     		int k;									 		
  101.     		for(k = 0; k < directions; k++)
  102. 			{					
  103.        			Step ss = Step(s1.x + tdirs[k][0], s1.y + tdirs[k][1]);	//s暫存第一條出路的下一個朝k方向移動後的座標 
  104.         			if(ss.x > -1 && ss.x < n &&	ss.y > -1 && ss.y < n ) //檢查s朝k方向移動後是否在合理的位子
  105. 					{
  106. 						if(!board[ss.x][ss.y]) 
  107. 						{
  108.             			minPossibleSteps[k] = 1;						//若合理，k方向就紀錄可以走 
  109.         				}		
  110. 	   				}
  111. 			}
  112.     		int minIndex,i;												//兩個變數，minIndex是最小出路陣列的索引值、i是計數器
  113.  
  114. 			for(minIndex = 0, i = 1; i < count(possibleSteps); i++) 
  115. 			{ 
  116.        			int nextPossibleSteps[directions] = {0};      			 //設一個歸零過的一維陣列(大小為8)暫存第2條以上出路的可走方向 
  117.        			Step s2 = Step();
  118. 				s2.get(current, possibleSteps, i + 1);  				 //設s2來接下一個出路的座標。(get的第三個參數可以說是往第幾個出路移動) 	
  119. 				int k;											
  120.     			for(k = 0; k < directions; k++) 						//將可走方向記錄到一維陣列裡
  121. 				{						 
  122.        				Step sss = Step(s2.x + tdirs[k][0], s2.y + tdirs[k][1]); 	
  123.        				if(sss.x > -1 && sss.x < n && sss.y > -1 && sss.y < n )
  124.        				{
  125. 	    	   			if(!board[sss.x][sss.y]) 
  126. 						{
  127.    		         		nextPossibleSteps[k] = 1;
  128.         				}	
  129.        				}       		
  130. 				}	
  131.         			if(count(nextPossibleSteps) < count(minPossibleSteps)) 
  132. 					{
  133.             			minIndex = i;										//i代表比第一個出路後的座標還擁有最少出路的第i個座標，索引值放進minIndex
  134.             			int j;												//變數j作為計數器
  135.             			for(j = 0; j < directions; j++) 
  136. 						{													//把該座標哪些方向可通洗進去minPossibleSteps[j]
  137.              		 	  	minPossibleSteps[j] = nextPossibleSteps[j];
  138.             			}
  139.         			}
  140.    			}											//end_for其他出路與決定要走哪個出路跑完  
  141. 	current.get(current, possibleSteps, minIndex+1);
  142.     	}//end_else											
  143. board[current.x][current.y] = st;						/*將當前步數位置設定到棋盤上*/
  144.  
  145. 	}													/*結束for迴圈*/
  146.  
  147.     int b;												/*印出board*/
  148.     for(b = 0; b < n; b++) {
  149.         int j;
  150.         for(j = 0; j < n; j++) {
  151.             printf("%3d", board[b][j]);
  152.         }
  153. 	      printf("\n");
  154.   	  }
  155.  
  156. delete [] board;
  157.  
  158. }														/*結束travel函式*/	
  159.  
  160. int main() {
  161.  
  162.     travel(5);
  163.     return 0;
  164. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  1 14  9 20  3
 24 19  2 15 10
 13  8 25  4 21
 18 23  6 11 16
  7 12 17 22  5
https://ideone.com/zTs5LA
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!