Source code for submission s1252

grasshop.cpp

  1. #include<cstdlib>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5.  
  6.  
  7.  
  8. int r,c,gr,gc,lr,lc;
  9. int table[100][100];
  10. int fronta[10010];
  11. int fR,fW;
  12.  
  13. bool possible(int a1, int a2){
  14. 	if(a1<r&&a1>=0&&a2>=0&&a2<c)return true;
  15. 	return false;
  16. }
  17.  
  18. int main()
  19. {
  20. while(scanf("%d%d%d%d%d%d",&r,&c,&gr,&gc,&lr,&lc)==6){
  21. 	fR=fW=0;
  22. 	lr--;lc--;gr--;gc--;
  23. 	for(int i=0;i<100;i++){
  24. 		for(int j=0;j<100;j++){
  25. 			if(i<r && j<c)table[i][j]=200;
  26. 			else table[i][j]=-1;
  27. 		}
  28. 	}
  29. 	int hops = -1;
  30. 	//printf("gr%d gc%d\n",gr,gc);
  31. 	table[gr][gc] = 0;
  32. 	fronta[fW++]=100*gr+gc;
  33. 	int actual,actTable;
  34. 	int actR,actC;
  35. 	while(fR!=fW){
  36. 		//printf("ctu frontu %d\n",fR);
  37. 		actual = fronta[fR++];
  38. 		//printf("ctu frontu %d\n",actual);
  39. 		actC = actual%100;
  40. 		actR = actual/100;
  41. 		actTable = table[actR][actC];
  42. 		//printf("Jsem v %d %d po %d skocich\n",actR,actC,actTable);
  43. 		if(actC==lc && actR==lr){
  44. 			hops = table[actR][actC];
  45. 			break;
  46. 		}
  47. 		if(possible(actR+1,actC+2)){
  48. 			if(actTable+1 < table[actR+1][actC+2]){
  49. 				table[actR+1][actC+2]=actTable+1;
  50. 				//printf("frontim na %d\n",fW);
  51. 				fronta[fW++]=(actR+1)*100+actC+2;
  52. 			}
  53. 		}
  54. 		if(possible(actR+2,actC+1)){
  55. 			if(actTable+1 < table[actR+2][actC+1]){
  56. 				table[actR+2][actC+1]=actTable+1;
  57. 				//printf("frontim na %d\n",fW);
  58. 				fronta[fW++]=(actR+2)*100+actC+1;
  59. 			}
  60. 		}
  61. 		if(possible(actR-1,actC+2)){
  62. 			if(actTable+1 < table[actR-1][actC+2]){
  63. 				table[actR-1][actC+2]=actTable+1;
  64. 				//printf("frontim na %d\n",fW);
  65. 				fronta[fW++]=(actR-1)*100+actC+2;
  66. 			}
  67. 		}
  68. 		if(possible(actR+1,actC-2)){
  69. 			if(actTable+1 < table[actR+1][actC-2]){
  70. 				table[actR+1][actC-2]=actTable+1;
  71. 				//printf("frontim na %d\n",fW);
  72. 				fronta[fW++]=(actR+1)*100+actC-2;
  73. 			}
  74. 		}
  75. 		if(possible(actR-2,actC+1)){
  76. 			if(actTable+1 < table[actR-2][actC+1]){
  77. 				table[actR-2][actC+1]=actTable+1;
  78. 				//printf("frontim na %d\n",fW);
  79. 				fronta[fW++]=(actR-2)*100+actC+1;
  80. 			}
  81. 		}
  82. 		if(possible(actR+2,actC-1)){
  83. 			if(actTable+1 < table[actR+2][actC-1]){
  84. 				table[actR+2][actC-1]=actTable+1;
  85. 				//printf("frontim na %d\n",fW);
  86. 				fronta[fW++]=(actR+2)*100+actC-1;
  87. 			}
  88. 		}
  89. 		if(possible(actR-1,actC-2)){
  90. 			if(actTable+1 < table[actR-1][actC-2]){
  91. 				table[actR-1][actC-2]=actTable+1;
  92. 				//printf("frontim1 na %d\n",fW);
  93. 				fronta[fW++]=(actR-1)*100+actC-2;
  94. 				//printf("frontim1 na %d %d\n",fW,fronta[fW]);
  95. 			}
  96. 		}
  97. 		if(possible(actR-2,actC-1)){
  98. 			if(actTable+1 < table[actR-2][actC-1]){
  99. 				table[actR-2][actC-1]=actTable+1;
  100. 				//printf("frontim2 na %d\n",fW);
  101. 				fronta[fW++]=(actR-2)*100+actC-1;
  102. 			}
  103. 		}
  104. 	}
  105. 	if(hops==-1)printf("impossible\n");
  106. 	else{printf("%d\n",hops);}
  107. }
  108. return 0;
  109. }
  110.  
  111. /*
  112.  
  113. for(int i=0;i<10;i++)
  114. {
  115.  
  116. 	 }
  117.  
  118. scanf("%d",&);
  119. printf("%d");
  120.  
  121.  
  122.  
  123. */
  124.