[Spoj] Wandering Queen

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Wandering Queen
Source            : Spoj
Category          : Graph Theory
Algorithm         : spfa
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define FOR(i, n)                 for (int i = 1; i <= n; i++)
#define For(i, n)                 for (size_t i = 0; i < n; i++)
 
#define inf                       12345678
 
static const int maxn = 1000 + 5;
 
int dr[] = {0, 0, 1, -1, 1, 1, -1, -1};  // 8 Direction
int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
 
struct info
{
    int x, y;
    info(int x = 0, int y = 0) : x(x), y(y) {}
};
 
int row, column;
int dis[maxn][maxn];
bool now[maxn][maxn];
char grid[maxn][maxn];
 
bool inside(int r, int c)
{
    return r >= 1 && r <= row && c >= 1 && c <= column;
}
 
int spfa(info src, info des)
{
    FOR(i, row) FOR(j, column) dis[i][j] = inf, now[i][j] = 0;
    queue <info> PQ;
    PQ.emplace(src);
    dis[src.x][src.y] = 0;
    now[src.x][src.y] = 1;
    while(!PQ.empty())
    {
        info u = PQ.front(); PQ.pop();
        now[u.x][u.y] = 0;
        For(i, 8)
        {
            bool push = false;
            int prex = u.x, prey = u.y;
            while (true)
            {
                int x = prex + dr[i];
                int y = prey + dc[i];
                if (!inside(x, y) || grid[x][y] == 'X') break;
                if (dis[x][y] >= dis[u.x][u.y] + 1)
                {
                    dis[x][y] = dis[u.x][u.y] + 1;
                    if (!now[x][y]) now[x][y] = 1, PQ.emplace(x, y);
                    prex = x, prey = y;
                }
                else break;
            }
        }
    }
    if (dis[des.x][des.y] == inf) return -1;
    return dis[des.x][des.y];
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tc;
    cin >> tc;
    FOR(tcase, tc)
    {
        cin >> row >> column;
        info s, t;
        FOR(i, row)
        {
            FOR(j, column)
            {
                cin >> grid[i][j];
                if (grid[i][j] == 'S') s.x = i, s.y = j;
                if (grid[i][j] == 'F') t.x = i, t.y = j;
            }
        }
        int ans = spfa(s, t);
        cout << ans << endl;
    }
}