Source code for submission s980

Go to diff to previous submission

grasshop5.cpp

  1. #include <iostream>
  2. #include <queue>
  3. #include <limits.h>
  4. #include <stdio.h>
  5.  
  6. using namespace std;
  7.  
  8. int ** ARRAY;
  9. int SIZEX;
  10. int SIZEY;
  11. int leafx, leafy;
  12. bool ISEND;
  13.  
  14. class item {
  15. 	public:
  16. 	item(int x,int y, int count);
  17. 	int X, Y, count;
  18. };
  19.  
  20. item::item(int x,int y, int count)
  21. {
  22. this->X=x;
  23. this->Y=y;
  24. this->count=count;
  25. }
  26.  
  27. queue <item> fronta;
  28.  
  29. void insert(int X, int Y, int count);
  30.  
  31. void jump (item mItem) {
  32. 	if(mItem.X==(leafx-1) && mItem.Y==(leafy-1))
  33. 	{
  34. 		ISEND=true;
  35. 		cout << mItem.count << endl;
  36. 		return;
  37. 	}
  38. 	insert(mItem.X+1,mItem.Y+2, mItem.count+1);
  39. 	insert(mItem.X+2,mItem.Y+1, mItem.count+1);
  40. 	insert(mItem.X+2,mItem.Y-1, mItem.count+1);
  41. 	insert(mItem.X+1,mItem.Y-2, mItem.count+1);
  42. 	insert(mItem.X-1,mItem.Y-2, mItem.count+1);
  43. 	insert(mItem.X-2,mItem.Y-1, mItem.count+1);
  44. 	insert(mItem.X-2,mItem.Y+1, mItem.count+1);
  45. 	insert(mItem.X-1,mItem.Y+2, mItem.count+1);
  46.  
  47. }
  48.  
  49. void insert(int X, int Y, int count)
  50. {
  51. 	if(X<0 || X>=SIZEX || Y<0 || Y>=SIZEY || count >= ARRAY[X][Y])
  52. 	return;
  53. 	ARRAY[X][Y]=count;
  54. 	fronta.push(item(X, Y, count));
  55. }
  56.  
  57. int main() {
  58. 	int grex, grey;
  59.  
  60. 	while(scanf("%d %d %d %d %d %d\n", &SIZEX, &SIZEY, &grex, &grey,  &leafx, &leafy)==6)
  61. 	{
  62. 		ARRAY=new int *[SIZEX];
  63. 		for (int i=0; i<SIZEX; i++) 
  64. 		{
  65. 			ARRAY[i]=new int [SIZEY];
  66. 			for (int j=0; j<SIZEY; j++)
  67. 			{
  68. 				ARRAY[i][j]=INT_MAX;
  69. 			}
  70. 		}
  71. 		ISEND=false;
  72. 		insert(grex-1, grey-1, 0);
  73. 		do
  74. 		{
  75. 		jump(fronta.front());
  76. 		fronta.pop();
  77. 		} while(!fronta.empty() && !ISEND);
  78. 		if(fronta.empty() && !ISEND) printf("impossible\n");
  79. 		while(!fronta.empty())
  80. 		{
  81. 			fronta.pop();
  82. 		}
  83. 	}
  84.  
  85. 	return 0;
  86. }
  87.  
  88.  
  89.  
  90.  
  91.  

Diff to submission s653

grasshop.cpp

--- c4.s653.cteam009.grasshop.cpp.0.grasshop.cpp
+++ c4.s980.cteam009.grasshop.cpp.0.grasshop5.cpp
@@ -1,53 +1,63 @@
-#include <stdio.h>
-#include <limits.h>
 #include <iostream>
+#include <queue>
+#include <limits.h>
+#include <stdio.h>
+
+using namespace std;
 
 int ** ARRAY;
 int SIZEX;
 int SIZEY;
-int MINCOUNT;
 int leafx, leafy;
-/*
-int min(int & X, int & Y)
-{
-        if(X>Y) return Y;
-        else return X;
-}
-*/
-void jump(int X, int Y, int count)
-{
-if(X==(leafx-1) && Y==(leafy-1))
+bool ISEND;
+
+class item {
+        public:
+        item(int x,int y, int count);
+        int X, Y, count;
+};
+
+item::item(int x,int y, int count)
 {
-        if(count < MINCOUNT)
-        {
-                ARRAY[X][Y]=count;
-                MINCOUNT=count;
-        }
-        return;
+this->X=x;
+this->Y=y;
+this->count=count;
 }
 
-if(X<0 || X>=SIZEX || Y<0 || Y>=SIZEY || count >= ARRAY[X][Y] || count>=MINCOUNT)
-return;
+queue <item> fronta;
 
-ARRAY[X][Y]=count;
+void insert(int X, int Y, int count);
 
-jump(X+1,Y+2, count+1);
-jump(X+2,Y+1, count+1);
-jump(X+2,Y-1, count+1);
-jump(X+1,Y-2, count+1);
-jump(X-1,Y-2, count+1);
-jump(X-2,Y-1, count+1);
-jump(X-2,Y+1, count+1);
-jump(X-1,Y+2, count+1);
+void jump (item mItem) {
+        if(mItem.X==(leafx-1) && mItem.Y==(leafy-1))
+        {
+                ISEND=true;
+                cout << mItem.count << endl;
+                return;
+        }
+        insert(mItem.X+1,mItem.Y+2, mItem.count+1);
+        insert(mItem.X+2,mItem.Y+1, mItem.count+1);
+        insert(mItem.X+2,mItem.Y-1, mItem.count+1);
+        insert(mItem.X+1,mItem.Y-2, mItem.count+1);
+        insert(mItem.X-1,mItem.Y-2, mItem.count+1);
+        insert(mItem.X-2,mItem.Y-1, mItem.count+1);
+        insert(mItem.X-2,mItem.Y+1, mItem.count+1);
+        insert(mItem.X-1,mItem.Y+2, mItem.count+1);
 
 }
 
-int main()
+void insert(int X, int Y, int count)
 {
+        if(X<0 || X>=SIZEX || Y<0 || Y>=SIZEY || count >= ARRAY[X][Y])
+        return;
+        ARRAY[X][Y]=count;
+        fronta.push(item(X, Y, count));
+}
+
+int main() {
         int grex, grey;
 
         while(scanf("%d %d %d %d %d %d\n", &SIZEX, &SIZEY, &grex, &grey,  &leafx, &leafy)==6)
         {
-                MINCOUNT=INT_MAX;
                 ARRAY=new int *[SIZEX];
                 for (int i=0; i<SIZEX; i++) 
@@ -59,10 +69,22 @@
                         }
                 }
-                jump(grex-1,grey-1,0);
-        if(ARRAY[leafx-1][leafy-1]==INT_MAX)
-        printf("impossible\n");
-        else printf("%d\n", ARRAY[leafx-1][leafy-1]);   
+                ISEND=false;
+                insert(grex-1, grey-1, 0);
+                do
+                {
+                jump(fronta.front());
+                fronta.pop();
+                } while(!fronta.empty() && !ISEND);
+                if(fronta.empty() && !ISEND) printf("impossible\n");
+                while(!fronta.empty())
+                {
+                        fronta.pop();
+                }
         }
 
-return 0;
+        return 0;
 }
+
+
+
+