LightOJ 1066 Gathering Food

//Unsorted Ideas: 
ফুড কালেক্ট করা লাগবে। গ্রিড আছে। গ্রিডে হ্যাশ আছে, ডট আছে , আপারকেস লেটার আছে ।
লেটার মানে ফুড । A থেকে শুরু করে বিভিন্ন লেটার পর্যন্ত থাকতে পারে তবে সব সিকুয়েনশিয়ালি একটার পর একটা থাকবে তবে বিভিন্ন পজিশানে।

এখন আমরা A থেকে শুরু করব লাস্ট ক্যারেক্টার পর্যন্ত সবগুলো ফুড কালেক্ট করব শরটেস্ট টাইমে। কিন্তু কন্সট্রেইন্টস হল - আগে ছোট ক্যারেক্টারের ফুড কালেক্ট করে তারপর বড় ক্যারেক্টার এ যেতে পারব।

এখন আমরা যদি A থেকে শুরু করে লাস্ট ডেসিটিনেশান ক্যারেক্টার পর্যন্ত একটা বিএফেস চালায়ে শরটেস্ট পাথ বের করি তাহলে লাভ নাই। কারন এখানে কোন পাথে সোর্স থেকে ডেস্টিনেশানে যাব সেটা ফিক্স করা আছে।

এখন এরকম ক্ষেত্রে যেটা করে যায় সেটা হচ্ছে, ঐ ফিক্স করা পাথ ধরে আগাতে পারি। ওই পাথের প্রতি দুইটা নোড কে একবার সোর্স আরেকবার ডেস্টিনেশান ধরে ধরে সামনে যেতে পারি।

আর যাবার সময় কস্ট যোগ করে করে রেখে যেতে পারি । প্রতিবার বিএফেস শেষে যখনি আমরা পরের লেটার পেয়ে যাচ্ছি, তখনি সেটাকে নেক্সট বিএফেস এর সোর্স বানিয়ে দিয়ে আবার নতুন বিএফস চালাব। এভাবে করে যেতে থাকব যতক্ষন লাস্ট ক্যারেক্টার পর্যন্ত পৌছাতে না পারি।

এখানে, একটা লক্ষণীয় ব্যাপার আছে,
ইনভেলিড সেল হিসেব করার সময়... গ্রিডের বাইরে গেলে ইনভ্যালিড, # পেলে ইনভ্যালিড অ্যান্ড ঐ যে, ডেস্টিনেশান এর চাইতে বড় কোন ক্যারেক্টার পেলেও ইনভ্যালিড, তবে আমরা চাইলে পুরানো ভিজিট করে আসা ছোট কোন ক্যারেক্টার আবার ইউজ করে যেতে পারি ।

ডিরেকশান অ্যাারে তা চার পাশ চেক দিতে হবে উপরের ভ্যলিডিটি গুলা ঠিক রেখে যদি সামনে যেতে পারি, তবেই আমরা আবার কিউ তে পুশ করব নতুবা না ।

Code:

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912
#define sz 13

ll n;
string sa[sz];
int d[sz][sz];
bool vis[sz][sz];
char destination;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

struct point
{
    int x,y;
};

point src;

void initt()
{
    REP(i,sz) REP(j,sz) vis[i][j] = 0, d[i][j] = INT_MAX;
}

int BFS(point s)
{
    initt();

    queue<point> Q;
    Q.push(s);

    vis[s.x][s.y] = 1;
    d[s.x][s.y] = 0;

    point u,v;

    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();

        if(sa[u.x][u.y]==destination)
        {
            src.x = u.x;
            src.y = u.y;
            
            return d[u.x][u.y];
        }
        
        REP(i,4)
        {
            v.x = u.x + dx[i];
            v.y = u.y + dy[i];

            if(v.x>=0 and v.x<n and v.y>=0 and v.y<n  and vis[v.x][v.y]==0)
            {
                 //give boundary chk first
                //then chk for xtra contraints
                
                if((sa[v.x][v.y]>destination and destination<='Z') or sa[v.x][v.y]=='#')

                {

                     continue;

                }                          

                vis[v.x][v.y] = 1;
                d[v.x][v.y] = d[u.x][u.y] + 1;
                Q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    ll t,cs=0;
    scl(t);
    while(t--)
    {
        scl(n);
        REP(i,n) cin>>sa[i];

        int cnt = 0;

        REP(i,n)
        {
            REP(j,n)
            {
                if(sa[i][j]=='A') src.x=i, src.y=j;
                if(isupper(sa[i][j])) cnt++;
            }
        }

        int cst=0, res = 0;
        destination = 'B';

        printf("Case %lld: ",++cs);

        //below used cnt-1
        //for value cnt==1,for only A is present
        //it doesnt enter loop,so print automatic 0 for this

        REP(i,cnt-1)
        {
            cst = BFS(src);
            
            if(cst==-1)
            {
                puts("Impossible");
                break;
            }
            else res += cst;

            destination++;
        }
        if(cst!=-1) printf("%d\n", res);
    }
    return 0;
}