fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // debug:
  5. #ifndef ONLINE_JUDGE
  6. #include "D:\Problem Solving\Imp files - PDFs - Books\debug\debug.hpp"
  7. #else
  8. #define debug(...)
  9. #define debug_itr(...)
  10. #define debug_bits(...)
  11. #endif
  12.  
  13. const double PI = acos(-1.0);
  14. const double EPS = 1e-8; /// WARNING: problem dependent !!!
  15.  
  16. typedef long long ll;
  17. typedef vector< vector<int> > GRAPH;
  18.  
  19. #define Saeed_fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
  20. #define endl '\n'  // because '\n' is faster while compiling, and 'endl' is easier for coding ;)
  21. #define all(c) (c).begin(), (c).end()
  22. #define all1(a, n) ((a).begin() + 1), ((a).begin() + (n) + 1)
  23. #define for1(iter, n) for (int (iter) = 1; (iter) <= (n); ++(iter))
  24.  
  25. inline void yes_or_no(bool ok) { cout << (ok? "YES\n" : "NO\n"); }
  26. inline ll sum_to_n(ll n) { return n*(n + 1)/2; }
  27. // double compare
  28. // returns: 0 if almost equal, 1 if `a` greater, -1 if `b` greater
  29. inline int dcmp (double a, double b) { return fabs(a - b) <= EPS? 0 : a > b? 1 : -1; }
  30.  
  31. /////
  32.  
  33. int n, m;
  34. vector<string> grid;
  35. pair<int, int> s, f;
  36. vector< vector<int> > moves;
  37.  
  38. struct cell { int i, j; };
  39.  
  40. /// save
  41. int dr[8] = {-1, 1, 0, 0, 1, 1, -1, -1};
  42. int dc[8] = {0, 0, -1, 1, 1, -1, 1, -1};
  43.  
  44. /// save
  45. bool is_valid(int i, int j) {
  46.     return (i >= 0 and i < n) and (j >= 0 and j < m);
  47. }
  48. void bfs() {
  49.     queue<cell> breadth;
  50.     vector< vector<bool> > added(n, vector<bool>(m));
  51.  
  52.     cell start = {s.first, s.second};
  53.     breadth.push(start);
  54.     added[start.i][start.j] = true;
  55.  
  56.     for (int level = 0, siz = breadth.size(); !breadth.empty(); ++level, siz = breadth.size()) {
  57.         while (siz--) { // process only the current level
  58.             auto cur = breadth.front(); /// save
  59.             breadth.pop();
  60.  
  61.             // get neighbors
  62.             for (int i = 0; i < 8; ++i) {
  63.                 int ni = cur.i + dr[i], nj = cur.j + dc[i];
  64.  
  65.                 // move the queen to the end of the direction
  66.                 int val = moves[cur.i][cur.j] + 1;
  67.                 while (is_valid(ni, nj) and grid[ni][nj] != 'X' and !(added[ni][nj] and moves[ni][nj] < val)) {
  68.                     moves[ni][nj] = val;
  69.                     breadth.push({ni, nj});
  70.                     added[ni][nj] = true;
  71.                     ni += dr[i], nj += dc[i];
  72.                 }
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. void solve(int TC) {
  79.     cin >> n >> m;
  80.     grid = vector<string>(n);
  81.     for (int i = 0; i < n; ++i) {
  82.         cin >> grid[i];
  83.     }
  84.     for (int i = 0; i < n; ++i) {
  85.         for (int j = 0; j < m; ++j) {
  86.             if (grid[i][j] == 'S')
  87.                 s = {i, j};
  88.             else if (grid[i][j] == 'F')
  89.                 f = {i, j};
  90.         }
  91.     }
  92.  
  93.     moves = vector< vector<int> >(n, vector<int>(m, 100000));
  94.     moves[s.first][s.second] = 0;
  95.     bfs();
  96.  
  97.     int ans = moves[f.first][f.second] == 100000? -1 : moves[f.first][f.second];
  98.     cout << ans << endl;
  99. }
  100.  
  101. int main()
  102. {
  103.     Saeed_fast;
  104.  
  105.     int TC = 1;
  106.     cin >> TC;
  107.     for (int test = 1; test <= TC; ++test) {
  108.         solve(test);
  109.     }
  110.  
  111.     return 0;
  112. }
Runtime error #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/62v7j6
problem QUEEN, based on SPOJ submission 31658080 (CPP14), 2023-07-29 18:13:43
language:
C++14 (gcc 8.3)
created:
277 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!