Help me find bug in this please [Nurikabe puzzle validator]

Revision en1, by cold.coffee., 2022-09-08 14:10:27

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";
    }
}
Tags graphs, floodfill

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English cold.coffee. 2022-09-08 14:10:27 3303 Initial revision (published)