Labirint2_Of

#include <fstream>
#include <queue>
using namespace std;

ifstream fin ("labirint2.in");
ofstream fout ("labirint2.out");

const int N = 405;

int dx[10][10], dy[10][10], n, b, s, k, a[N][N];
short d[N][N];
queue <pair <int, int> > Q;

int main() {
    fin >> n >> b >> s >> k;
    for (int x, y, i = 0; i < b; ++i) {
        fin >> x >> y;
        a[x-1][y-1]++;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (a[i][j] != 1)
                a[i][j] = 0;
    for (int i = 0; i < s; ++i)
        for (int j = 0; j < k; ++j) {
            string s;
            fin >> s;
            if (s == "L")
                dx[i][j] = 0, dy[i][j] = -1;
            if (s == "R")
                dx[i][j] = 0, dy[i][j] = 1;
            if (s == "U")
                dx[i][j] = -1, dy[i][j] = 0;
            if (s == "D")
                dx[i][j] = 1, dy[i][j] = 0;
        }
    Q.push(make_pair (0, 0));
    d[0][0] = 1;
    while (Q.size()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        int xx = x;
        int yy = y;
        for (int i = 0; i < s; ++i) {
            xx = x;
            yy = y;
            bool ok = 1;
            for (int j = 0; j < k; ++j) {
                xx += dx[i][j];
                yy += dy[i][j];
                if (xx < 0 || yy < 0 || xx >= n || yy >= n || a[xx][yy]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && !d[xx][yy]) {
                d[xx][yy] = d[x][y] + 1;
                Q.push(make_pair (xx, yy));
            }
        }
    }
    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            fout << a[i][j] << " ";
        fout << "\n";
    }
    fout << "\n";*/
    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            fout << d[i][j] << " ";
        fout << "\n";
    }*/
    if (!d[n-1][n-1])
        fout << "Imposibil!";
    else
        fout << d[n-1][n-1] - 1;
}