The Great Wall Game (UVA 1045, UVALive 3276, World Finals >> 2005 - Shanghai)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100000

int dist[16][16][16], n, dp[(1<<15)+2][16];
vector<int>xx, yy;

void calculateDist(int pos, int x, int y)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            dist[pos][i][j] = abs(x-i)+abs(y-j);
            //cout<<pos<<" "<<i<<" "<<j<<" "<<dist[pos][i][j]<<endl;
        }
return;
}

int func(int mask, int pos)
{
    if(pos>=n) return 0;

    int &ret=dp[mask][pos];
    if(ret!=-1) return ret;

    ret=1e9;
    for(int i=0;i<n;i++)
    {
        if(!(mask & (1<<i)))
        {
            ret = min(ret, dist[i][xx[pos]][yy[pos]]+func(mask | (1<<i), pos+1));
        }
    }
return ret;
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, x, y, mn;
    while(cin>>n && n)
    {
        mn=1e9;
        for(int i=0;i<n;i++)
        {
            cin>>x>>y;
            x--, y--;
            calculateDist(i, x, y);
        }
        //row
        for(int row=0;row<n;row++)
        {
            xx.clear();
            yy.clear();
            for(int col=0;col<n;col++)
            {
                xx.push_back(row);
                yy.push_back(col);
            }
            SET(dp);
            mn=min(mn, func(0, 0));
            //cout<<mn<<endl;
        }
        //col
        for(int col=0;col<n;col++)
        {
            xx.clear();
            yy.clear();
            for(int row=0;row<n;row++)
            {
                xx.push_back(row);
                yy.push_back(col);
            }
            SET(dp);
            mn=min(mn, func(0, 0));
            //cout<<mn<<endl;
        }
        //diagonal1
        xx.clear();
        yy.clear();
        for(int row=0, col=0;row<n;row++, col++)
        {
            xx.push_back(row);
            yy.push_back(col);
        }
        SET(dp);
        mn=min(mn, func(0, 0));
        //diagonal2
        xx.clear();
        yy.clear();
        for(int row=0, col=n-1;row<n;row++, col--)
        {
            xx.push_back(row);
            yy.push_back(col);
        }
        SET(dp);
        mn=min(mn, func(0, 0));

        cout<<"Board "<<kk++<<": "<<mn<<" moves required.\n\n";
    }
return 0;
}