Nurikabe puzzle validator

Viewed 43

I've been trying to write a validator for Nurikabe puzzle. Online Judge Link

While I'm seeing a lot of my test cases passing, there's seem to be some issue with the code due to which some of the test cases are failing. I've tried playing around with the implementation (without a clue) but nothing seem to be working.

Since I do not have access to the failing test cases, I'm hoping to get an input here. Could someone point out the mistake in the code or any corner cases I'm missing?

int r, c, n;
int t, a, b, k, shade, unshade, full, x, y, ct, connect;
vector<string> board;
vector<pair<pair<int, int>, int>> in;
int vis[105][105];

void dfs1(int x, int y, char c)
{
    if (x < 0 || x >= r || y < 0 || y >= c || vis[x][y] == 1 || board[x][y] != c)
        return;

    vis[x][y] = 1;
    ct--;

    dfs1(x, y + 1, c);
    dfs1(x + 1, y, c);
    dfs1(x - 1, y, c);
    dfs1(x, y - 1, c);
}

void dfs2(int x, int y)
{
    if (x < 0 || x >= r || y < 0 || y >= c || vis[x][y] == 1 || board[x][y] != '.')
        return;

    if (x == 0 || y == 0 || x == r - 1 || y == c - 1)
        connect = 1;

    vis[x][y] = 1;

    dfs2(x, y + 1);
    dfs2(x + 1, y);
    dfs2(x - 1, y);
    dfs2(x, y - 1);
    dfs2(x + 1, y + 1);
    dfs2(x + 1, y - 1);
    dfs2(x - 1, y + 1);
    dfs2(x - 1, y - 1);
}

bool check1(int x, int y)
{
    ct = shade;
    dfs1(x, y, '#');
    return ct == 0;
}

bool check2()
{
    for (auto v : in)
    {
        ct = v.se;
        dfs1(v.fi.fi, v.fi.se, '.');
        if (ct != 0)
            return false;
    }
    return true;
}

bool check3()
{
    for (auto v : in)
    {
        connect = 0;
        fill(vis, 0);
        dfs2(v.fi.fi, v.fi.se);
        if (connect == 0)
            return false;
    }
    return true;
}

bool check4()
{
    int i, j;
    for (i = 0; i < r - 1; i++)
    {
        for (j = 0; j < c - 1; j++)
        {
            bool flag = (board[i][j] == '.' || board[i][j + 1] == '.' ||
                         board[i + 1][j] == '.' || board[i + 1][j + 1] == '.');
            if (flag == false)
                return 0;
        }
    }
    return 1;
}

int main()
{
    string line;
    cin >> t;
    while (t--)
    {
        board.clear();
        in.clear();
        fill(vis, 0);
        shade = unshade = full = 0;
        cin >> r >> c >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a >> b >> k;
            in.push_back({{a, b}, k});
            full += k;
        }
        for (int i = 0; i < r; i++)
        {
            cin >> line;
            board.push_back(line);
            for (int l = 0; l < line.size(); l++)
                if (line[l] == '#')
                {
                    shade++;
                    x = i, y = l;
                }
                else
                    unshade++;
        }

        if (full == unshade && check1(x, y) && check2() && check3() && check4())
            cout << "solved\n";
        else
            cout << "not solved\n";
    }
}
0 Answers
Related