Advertisement
Guest User

Untitled

a guest
May 20th, 2018
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1.  
  2. #include <vector>
  3. #include <algorithm>
  4. #include <fstream>
  5. #include<string>
  6. #include <iostream>
  7. using namespace std;
  8.  
  9. vector<vector<char> > x(1001, vector<char>(1001));
  10. vector<vector<int> > y(0, vector<int>(2)), rang(1001, vector<int >(1001, -1));
  11. vector<int> q(2);
  12. ifstream in("rook.in"); ofstream out("rook.out");
  13.  
  14.  
  15.  
  16. int main() {
  17.     vector<vector<int> > t(501, vector<int>(501, 0));
  18.     int n, m;
  19.     in >> n >> m;
  20.     string s;
  21.     vector<int> start(2), endd(2);
  22.     getline(in, s);
  23.     for (int i = n - 1; i >= 0; --i) {
  24.         for (int j = 0; j<m; j++) {
  25.             in >> x[i][j];
  26.             if (x[i][j] == 'S') { start[0] = i; start[1] = j; }
  27.             if (x[i][j] == 'F') { endd[0] = i; endd[1] = j; }
  28.  
  29.         }
  30.     }
  31.     int k = 0;
  32.     vector<int> q(2);
  33.     y.push_back(start);
  34.     rang[start[0]][start[1]] = 0;
  35.     while (k<y.size() ) {
  36.         if (t[y[k][0]][y[k][1]] == 0) {
  37.             t[y[k][0]][y[k][1]] = 1;
  38.             int i;
  39.             int j;
  40.             //cout<<k<<' '<<y[k][0]<<' '<<y[k][1]<<' '<<rang[y[k][0]][y[k][1]]<<endl;
  41.             for (i = y[k][0] + 1; i<n && (x[i][y[k][1]] != 'P'); i++) {
  42.  
  43.                 if (rang[i][y[k][1]] == -1) {
  44.                     q[0] = i;
  45.                     q[1] = y[k][1];
  46.                     y.push_back(q);
  47.                     rang[i][y[k][1]] = rang[y[k][0]][y[k][1]] + 1;
  48.                 }
  49.             }
  50.             for (i = y[k][0] - 1; i >= 0 && (x[i][y[k][1]] != 'P'); --i) {
  51.                 if (rang[i][y[k][1]] == -1) {
  52.                     q[0] = i;
  53.                     q[1] = y[k][1];
  54.                     y.push_back(q);
  55.                     rang[i][y[k][1]] = rang[y[k][0]][y[k][1]] + 1;
  56.                 }
  57.             }
  58.  
  59.  
  60.             for (j = y[k][1] - 1; j >= 0 && (x[y[k][0]][j] != 'P'); --j) {
  61.                 if (rang[y[k][0]][j] == -1) {
  62.                     q[1] = j;
  63.                     q[0] = y[k][0];
  64.                     y.push_back(q);
  65.                     rang[y[k][0]][j] = rang[y[k][0]][y[k][1]] + 1;
  66.                 }
  67.             }
  68.  
  69.             for (j = y[k][1] + 1; j<m && (x[y[k][0]][j] != 'P'); j++) {
  70.                 if (rang[y[k][0]][j] == -1) {
  71.                     q[1] = j;
  72.                     q[0] = y[k][0];
  73.                     y.push_back(q);
  74.                     rang[y[k][0]][j] = rang[y[k][0]][y[k][1]] + 1;
  75.                 }
  76.             }
  77.         }
  78.         k++;
  79.  
  80.     }
  81.     out << rang[endd[0]][endd[1]];
  82.     cin >> k;
  83.     return(0);
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement