b841: 104北二5.骨牌遊戲

#include <iostream>
#include <queue>

using namespace std;

#define VISITED -1

struct Node
{
    int x;
    int y;
    int level;
};

int findPairs( int** mat, int h, int w, int x, int y)
{
    int levelCount[2] = { 0, 0};  // even level and odd level
    int currValue = mat[x][y];

    // bfs starts from x, y
    Node n, nbr;
    n = (Node){.x = x, .y = y, .level = 1};

    queue<Node> q; // for bfs
    mat[x][y] = VISITED; // mark as visited
    levelCount[1] = 1;
    q.push( n);

    while( q.size() != 0)
    {
        n = q.front();
        q.pop();
        // check neighboors
        if( (n.x-1) >= 0 && mat[n.x-1][n.y] == currValue)
        {
            nbr = (Node){.x = n.x-1, .y = n.y, .level = n.level+1};
            q.push(nbr);
            mat[n.x-1][n.y] = VISITED; // mark as visited
            levelCount[nbr.level%2]++;
        }
        if( (n.x+1) < h &&  mat[n.x+1][n.y] == currValue)
        {
            nbr = (Node){.x = n.x+1, .y = n.y, .level = n.level+1};
            q.push(nbr);
            mat[n.x+1][n.y] = VISITED; // mark as visited
            levelCount[nbr.level%2]++;
        }
        if( (n.y-1) >= 0 &&  mat[n.x][n.y-1] == currValue)
        {
            nbr = (Node){.x = n.x, .y = n.y-1, .level = n.level+1};
            q.push(nbr);
            mat[n.x][n.y-1] = VISITED; // mark as visited
            levelCount[nbr.level%2]++;
        }
        if( (n.y+1) < w && mat[n.x][n.y+1] == currValue)
        {
            nbr = (Node){.x = n.x, .y = n.y+1, .level = n.level+1};
            q.push(nbr);
            mat[n.x][n.y+1] = VISITED; // mark as visited
            levelCount[nbr.level%2]++;
        }
    }

    if( levelCount[1] == 0)
        return 0;
    return min( levelCount[0], levelCount[1]);
}

int solver(int** mat, int h, int w)
{
    int count = 0;
    for( int i=0; i< h; i++)
    {
        for( int j=0; j< w; j++)
        {
            if( mat[i][j] != VISITED)
            {
                count += findPairs( mat, h, w, i, j);
            }
        }
    }
    return count;
}


int main()
{
    int ** mat;
    int w, h;

    cin >> h >> w;

    mat = new int*[h];

    for( int i=0; i< h; i++)
    {
        mat[i] = new int[w];
        for( int j=0; j< w; j++)
        {
            cin >> mat[i][j];
        }
    }

    int numPairs = solver( mat, h, w);

    cout << numPairs << endl;

    for( int i=0; i< h; i++)
    {
        delete [] mat[i];
    }
    delete [] mat;

    return 0;
}