Ideone.com

fork download

copy

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 7;
char grid[N][N];
bool vis[N][N], marked[N][N];
const map<char, vector<int>> paths = {
        {'U', {-1, 0}},
        {'D', {1, 0}},
        {'L', {0, -1}},
        {'R', {0, 1}}
};
int n, m;
 
void reSet()
{
    for (int i = 0; i < n + 7; i++)
    {
        for (int j = 0; j < n + 7; j++)
        {
            marked[i][j] = false;
            vis[i][j]= false;
        }
    }
}
 
bool eXit(int i, int j)
{
    return ((i <= 0) or (j <= 0) or (i > n) or (j > m));
}
 
bool markIt(int i, int j)
{
    if (marked[i][j]) return true;
    if (vis[i][j] or (grid[i][j] == '?')) return false;
 
    char direct = grid[i][j];
 
    int x = paths.at(direct)[0] + i;
    int y = paths.at(direct)[1] + j;
 
    if (eXit(x, y)) return true;
 
    marked[x][y] = markIt(x, y);
    vis[x][y] = true;
    return marked[x][y];
}
 
bool isOk(int i, int j)
{
    for (auto child: paths)
    {
        auto path = child.second;
        int x = path[0] + i;
        int y = path[1] + j;
 
        if (eXit(x, y) or marked[x][y]) continue;
 
        return true;
    }
    return false;
}
 
int solve()
{
    cin >> n >> m; 
 
    reSet();
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> grid[i][j];
        }
    }
 
    if (n * m == 1)
    {
        return 0;
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if ((grid[i][j] != '?') and (!vis[i][j]))
            {
                marked[i][j] = markIt(i, j);
                vis[i][j] = true;
            }
        }
    }
 
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (grid[i][j] == '?')
            {
                if (isOk(i, j))
                {
                    res += 1;
                }
            }
            else if (!marked[i][j])
            {
                res += 1;
            }
        }
    }
 
    return res;
 
 
    return 0;
}
 
int main()
{
    int t; cin >> t;
    while (t--)
    {
        cout << solve() << "\n";
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTiA9IDFlMyArIDc7CmNoYXIgZ3JpZFtOXVtOXTsKYm9vbCB2aXNbTl1bTl0sIG1hcmtlZFtOXVtOXTsKY29uc3QgbWFwPGNoYXIsIHZlY3RvcjxpbnQ+PiBwYXRocyA9IHsKICAgICAgICB7J1UnLCB7LTEsIDB9fSwKICAgICAgICB7J0QnLCB7MSwgMH19LAogICAgICAgIHsnTCcsIHswLCAtMX19LAogICAgICAgIHsnUicsIHswLCAxfX0KfTsKaW50IG4sIG07Cgp2b2lkIHJlU2V0KCkKewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuICsgNzsgaSsrKQogICAgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbiArIDc7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIG1hcmtlZFtpXVtqXSA9IGZhbHNlOwogICAgICAgICAgICB2aXNbaV1bal09IGZhbHNlOwogICAgICAgIH0KICAgIH0KfQoKYm9vbCBlWGl0KGludCBpLCBpbnQgaikKewogICAgcmV0dXJuICgoaSA8PSAwKSBvciAoaiA8PSAwKSBvciAoaSA+IG4pIG9yIChqID4gbSkpOwp9Cgpib29sIG1hcmtJdChpbnQgaSwgaW50IGopCnsKICAgIGlmIChtYXJrZWRbaV1bal0pIHJldHVybiB0cnVlOwogICAgaWYgKHZpc1tpXVtqXSBvciAoZ3JpZFtpXVtqXSA9PSAnPycpKSByZXR1cm4gZmFsc2U7CgogICAgY2hhciBkaXJlY3QgPSBncmlkW2ldW2pdOwoKICAgIGludCB4ID0gcGF0aHMuYXQoZGlyZWN0KVswXSArIGk7CiAgICBpbnQgeSA9IHBhdGhzLmF0KGRpcmVjdClbMV0gKyBqOwoKICAgIGlmIChlWGl0KHgsIHkpKSByZXR1cm4gdHJ1ZTsKCiAgICBtYXJrZWRbeF1beV0gPSBtYXJrSXQoeCwgeSk7CiAgICB2aXNbeF1beV0gPSB0cnVlOwogICAgcmV0dXJuIG1hcmtlZFt4XVt5XTsKfQoKYm9vbCBpc09rKGludCBpLCBpbnQgaikKewogICAgZm9yIChhdXRvIGNoaWxkOiBwYXRocykKICAgIHsKICAgICAgICBhdXRvIHBhdGggPSBjaGlsZC5zZWNvbmQ7CiAgICAgICAgaW50IHggPSBwYXRoWzBdICsgaTsKICAgICAgICBpbnQgeSA9IHBhdGhbMV0gKyBqOwoKICAgICAgICBpZiAoZVhpdCh4LCB5KSBvciBtYXJrZWRbeF1beV0pIGNvbnRpbnVlOwoKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKaW50IHNvbHZlKCkKewogICAgY2luID4+IG4gPj4gbTsgCgogICAgcmVTZXQoKTsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICB7CiAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPD0gbTsgaisrKQogICAgICAgIHsKICAgICAgICAgICAgY2luID4+IGdyaWRbaV1bal07CiAgICAgICAgfQogICAgfQoKICAgIGlmIChuICogbSA9PSAxKQogICAgewogICAgICAgIHJldHVybiAwOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBtOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBpZiAoKGdyaWRbaV1bal0gIT0gJz8nKSBhbmQgKCF2aXNbaV1bal0pKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBtYXJrZWRbaV1bal0gPSBtYXJrSXQoaSwgaik7CiAgICAgICAgICAgICAgICB2aXNbaV1bal0gPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIGludCByZXMgPSAwOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgewogICAgICAgIGZvciAoaW50IGogPSAxOyBqIDw9IG07IGorKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChncmlkW2ldW2pdID09ICc/JykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKGlzT2soaSwgaikpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmVzICs9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZiAoIW1hcmtlZFtpXVtqXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmVzICs9IDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIHJlczsKCgogICAgcmV0dXJuIDA7Cn0KCmludCBtYWluKCkKewogICAgaW50IHQ7IGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkKICAgIHsKICAgICAgICBjb3V0IDw8IHNvbHZlKCkgPDwgIlxuIjsKICAgIH0KICAgIHJldHVybiAwOwp9

Success #stdin #stdout 0.01s 5284KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/DE4Ht5

language:

C++14 (gcc 8.3)

created:

visibility:

public

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language