[UVa] 11882 - Biggest Number

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11882 - Biggest Number
Source            : UVa Online Judge
Category          : Backtrack with Pruning
Algorithm         : Backtrack with Pruning
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define memo(a, b)         memset(a, b, sizeof a)
#define pii                pair <int, int>
#define mk                 make_pair
#define ff                 first
#define ss                 second
#define sz(a)              a.size()
#define all(a)             a.begin(), a.end()
 
static const int maxn = 20;
 
int dr[] = {+0, +0, +1, -1};
int dc[] = {+1, -1, +0, +0};
 
int row, column;
bool vis[maxn][maxn], mark[maxn][maxn];
string largestnum;
char grid[maxn][maxn];
 
bool go(int r, int c)
{
    return r >= 1 && r <= row && c >= 1 && c <= column;
}
 
bool isless(string a, string b) // check a is less than b
{
    if (sz(a) < sz(b)) return 1;
    if (sz(a) == sz(b) && a < b) return 1;
    return 0;
}
 
string bfs(int sx, int sy)
{
    memo(mark, 0);
    queue <pii> PQ;
    PQ.emplace(sx, sy);
    mark[sx][sy] = 1;
    string num;
    while (!PQ.empty())
    {
        pii u = PQ.front(); PQ.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = u.ff + dr[i];
            int y = u.ss + dc[i];
            if (!go(x, y) || vis[x][y] || mark[x][y] || grid[x][y] == '#') continue;
            mark[x][y] = 1;
            num += grid[x][y];
            PQ.emplace(x, y);
        }
    }
    return num;
}
 
void dfs(int sx, int sy, string makenum)
{
    if (isless(largestnum, makenum)) // ans is less than current number
    {
        largestnum = makenum;
    }
    else
    {
        string canmake = bfs(sx, sy);
        if (sz(makenum) + sz(canmake) < sz(largestnum)) return;
        if (sz(makenum) + sz(canmake) == sz(largestnum))
        {
            sort(all(canmake));
            reverse(all(canmake)); // generating the best possible answer
            string marge = makenum + canmake;
            if (isless(marge, largestnum)) return;
        }
    }
    // Recursive Search
    for (int i = 0; i < 4; i++)
    {
        int x = sx + dr[i];
        int y = sy + dc[i];
        if (!go(x, y) || vis[x][y] || grid[x][y] == '#') continue;
        vis[x][y] = 1;
        dfs(x, y, makenum + grid[x][y]);
        vis[x][y] = 0;
    }
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    while (cin >> row >> column)
    {
        if (row + column == 0) break;
        for (int i = 1; i <= row; i++)
        {
        	for (int j = 1; j <= column; j++)
            {
            	cin >> grid[i][j];
            }
        }
        largestnum.clear();
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= column; j++)
            {
                if (grid[i][j] != '#')
                {
                    string t = "";
                    t += grid[i][j];
                    vis[i][j] = 1;
                    dfs(i, j, t);
                    vis[i][j] = 0;
                }
            }
        }
        cout << largestnum << endl;
        memo(vis, 0);
    }
}