Source code for submission s1028

Go to diff to previous submission

grasshop.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <queue>
  4. #include <set>
  5.  
  6.  
  7. struct XPoint{
  8. 	int r;
  9. 	int c;
  10. 	int delka;
  11.  
  12. 	XPoint(int i, int j, int k){
  13. 		r = i;
  14. 		c = j;
  15. 		delka = k;
  16. 	}
  17. };
  18.  
  19.  
  20. int main(){
  21.  
  22.     int rows, cols, gregrow, gregcol, leafrow, leafcol;
  23.     bool skok;
  24.     int delka;
  25.  
  26.     bool mapa[101][101];
  27.  
  28.     while(scanf("%d%d%d%d%d%d",&rows,&cols,&gregrow, &gregcol, &leafrow,&leafcol)==6){
  29. 		if(gregcol == leafcol && gregrow == leafrow){printf("0\n"); continue;}
  30.  
  31. 		std::queue<XPoint> fronta;
  32. 		skok = false;
  33. 		for(int i = 1; i <= rows; i++)
  34. 			for(int j = 1; j <= cols; j++)
  35. 				mapa[i][j] = false;
  36.  
  37. 		fronta.push(XPoint(gregrow,gregcol,0));
  38. 		mapa[gregrow][gregcol] = true;
  39.  
  40.  
  41. 		while(!fronta.empty()){
  42. 			XPoint t = fronta.front();
  43. 			fronta.pop();
  44.  
  45. 			delka = t.delka +1;
  46.  
  47. 			int r = t.r - 1;
  48. 			int c = t.c - 2;
  49. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  50. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  51.  
  52. 			r = t.r + 1;
  53. 			c = t.c - 2;
  54. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  55. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  56.  
  57. 			r = t.r -2;
  58. 			c = t.c +1;
  59. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  60. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  61.  
  62. 			r = t.r -2;
  63. 			c = t.c -1;
  64. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  65. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  66.  
  67. 			r = t.r +2;
  68. 			c = t.c +1;
  69. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  70. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  71.  
  72. 			r = t.r +2;
  73. 			c = t.c -1;
  74. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  75. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  76.  
  77. 			r = t.r +1;
  78. 			c = t.c +2;
  79. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  80. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  81.  
  82. 			r = t.r - 1;
  83. 			c = t.c + 2;
  84. 			if(r == leafrow && c == leafcol) {skok = true;break;}
  85. 			if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
  86. 		}
  87.  
  88. 		if(skok) printf("%d\n",delka);
  89. 		else printf("impossible\n");
  90.  
  91.     }
  92.  
  93.     return 0;
  94. }
  95.  

Diff to submission s999

grasshop.cpp

--- c4.s999.cteam033.grasshop.cpp.0.grasshop.cpp
+++ c4.s1028.cteam033.grasshop.cpp.0.grasshop.cpp
@@ -6,11 +6,11 @@
 
 struct XPoint{
-        int x;
-        int y;
+        int r;
+        int c;
         int delka;
         
         XPoint(int i, int j, int k){
-                x = i;
-                y = j;
+                r = i;
+                c = j;
                 delka = k;
         }
@@ -26,5 +26,7 @@
     bool mapa[101][101];
     
-    while(scanf("%d%d%d%d%d%d",&rows,&cols, &gregcol, &gregrow,&leafcol,&leafrow)==6){
+    while(scanf("%d%d%d%d%d%d",&rows,&cols,&gregrow, &gregcol, &leafrow,&leafcol)==6){
+                if(gregcol == leafcol && gregrow == leafrow){printf("0\n"); continue;}
+                
                 std::queue<XPoint> fronta;
                 skok = false;
@@ -43,43 +45,43 @@
                         delka = t.delka +1;
                         
-                        int x = t.x - 1;
-                        int y = t.y - 2;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        int r = t.r - 1;
+                        int c = t.c - 2;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x + 1;
-                        y = t.y - 2;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r + 1;
+                        c = t.c - 2;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x -2;
-                        y = t.y +1;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r -2;
+                        c = t.c +1;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x -2;
-                        y = t.y -1;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r -2;
+                        c = t.c -1;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x +2;
-                        y = t.y +1;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r +2;
+                        c = t.c +1;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x +2;
-                        y = t.y -1;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r +2;
+                        c = t.c -1;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x +1;
-                        y = t.y +2;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r +1;
+                        c = t.c +2;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                         
-                        x = t.x - 1;
-                        y = t.y + 2;
-                        if(x == leafrow && y == leafcol) {skok = true;break;}
-                        if(!mapa[x][y] && x >= 1 && x <= rows && y >= 1 && y <= cols) {fronta.push(XPoint(x,y,t.delka +1));mapa[x][y] = true;}
+                        r = t.r - 1;
+                        c = t.c + 2;
+                        if(r == leafrow && c == leafcol) {skok = true;break;}
+                        if(!mapa[r][c] && r >= 1 && r <= rows && c >= 1 && c <= cols) {fronta.push(XPoint(r,c,t.delka +1));mapa[r][c] = true;}
                 }