Source code for submission s672

Go to diff to previous submission

grasshop.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. #include <queue>
  5. #include <climits>
  6. #include <cstdio>
  7.  
  8.  
  9. using namespace std;
  10.  
  11. int field[105][105];
  12. bool vis[105][105];
  13. int x[] = {1,2,2,1,-1,-2,-2,-1};
  14. int y[] = {-2,-1,1,2,2,1,-1,-2};
  15.  
  16. int r,c,gx,gy,lx,ly;
  17.  
  18. bool check(int x, int y){
  19. if(x < 1 || x > c || y < 1 || y > r)
  20. return false;
  21. return true;
  22. }
  23.  
  24. int main(){
  25.  
  26. while(cin >> r >> c>>gy>>gx>>ly>>lx){
  27. for(int i = 0; i < r + 1; i++)
  28. for(int j = 0; j < c + 1; j++){
  29. vis[i][j] = false;
  30. field[i][j] = INT_MAX >> 1;
  31. }
  32.  
  33. queue < pair <int,int> > q;
  34. q.push( pair<int,int>(gx,gy) );
  35. field[gy][gx] = 0;
  36. vis[gy][gx] = true;
  37. bool ok = false;
  38.  
  39. pair<int,int> fq;
  40. while(!q.empty()){
  41. fq = q.front();
  42. q.pop();
  43.  
  44. if(fq.first == lx && fq.second == ly){
  45. ok = true;
  46. break;
  47. }
  48.  
  49. for(int i = 0; i < 8; i++){
  50. if(check(fq.first + x[i], fq.second + y[i]))
  51. if(!vis[fq.second + y[i]][fq.first + x[i]]){
  52. vis[fq.second + y[i]][fq.first + x[i]] = true;
  53. field[fq.second + y[i]][fq.first + x[i]] = field[fq.second][fq.first] + 1;
  54. q.push( pair<int,int>(fq.first + x[i],fq.second + y[i]) );
  55. }
  56. }
  57. }
  58. /*
  59. for(int i = 0; i < r + 1; i++){
  60. for(int j = 0; j < c + 1; j++){
  61. cout << field[i][j] << " ";
  62. }
  63. cout << endl;
  64. }
  65. */
  66.  
  67. if(ok)
  68. cout << field[ly][lx] << endl;
  69. else
  70. cout << "impossible" << endl;
  71.  
  72. }
  73.  
  74.  
  75.  
  76. return 0;
  77. }
  78.  

Diff to submission s636

grasshop.cpp

--- c4.s636.cteam042.grasshop.cpp.0.grasshop.cpp
+++ c4.s672.cteam042.grasshop.cpp.0.grasshop.cpp
@@ -17,5 +17,5 @@
 
 bool check(int x, int y){
-        if(x < 1 || x >= c || y < 1 || y >= r)
+        if(x < 1 || x > c || y < 1 || y > r)
                 return false;
         return true;
@@ -26,6 +26,8 @@
         while(cin >> r >> c>>gy>>gx>>ly>>lx){
                 for(int i = 0; i < r + 1; i++)
-                        for(int j = 0; j < c + 1; j++)
+                        for(int j = 0; j < c + 1; j++){
                                 vis[i][j] = false;
+                                field[i][j] = INT_MAX >> 1;                             
+                        }
 
                 queue < pair <int,int> > q;
@@ -54,4 +56,13 @@
                         }
                 }
+/*
+                for(int i = 0; i < r + 1; i++){
+                        for(int j = 0; j < c + 1; j++){
+                                cout << field[i][j] << " ";                             
+                        }
+                cout << endl;
+                }
+*/
+
                 if(ok)
                         cout << field[ly][lx] << endl;