Ligthoj 1238 - Power Puff Girls

By -
===================== Best Solution ===========================

/*
Lionel Messi is such a player that you may catch him, you may touch him, you may feel him
and definitely you may Love him.
Lionel Messi is Messi. A little Magician in this World.

*/

// Accepted by One BFS

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 30;

char adj[high][high];
int cost[high][high] , dir_x[4] = {-1, 1 , 0 , 0} , dir_y[4] = {0 , 0 , -1, 1};
bool visited[high][high];

void BFS(int x , int y , int row, int col)
{
    int ux , uy , vx , vy;

    queue<int>Q;

    visited[x][y] = true;
    cost[x][y] = 0;

    Q.push(x);
    Q.push(y);

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

        uy = Q.front();
        Q.pop();

        for(int i=0; i<4; i++)
        {
            vx = ux + dir_x[i];
            vy = uy + dir_y[i];

            if((vx>=0 && vx<row) && (vy >=0 && vy < col) && (adj[vx][vy] != '#' && adj[vx][vy] != 'm'))
            {
                if(!visited[vx][vy])
                {
                    cost[vx][vy] = cost[ux][uy] + 1;
                    visited[vx][vy] = true;
                    Q.push(vx);
                    Q.push(vy);
                }
            }
        }
    }
}

int main()
{
    //fast;
    int test, tc=0 , row , col , i , j , ha , hb, sa , ea , sb , eb , sc , ec , maxi = 0;
    char ch;
    sf("%d", &test);
    while(test--)
    {
        mset(adj , '#');
        mset(cost , 0);
        mset(visited , false);

        sf("%d %d", &row , &col);

        maxi = 0;

        for(i=0; i<row; i++)
        {
            for(j=0; j<col; j++)
            {
                sf(" %c", &ch);

                if(ch == 'a')
                {
                    sa = i;
                    ea = j;
                }

                if(ch == 'b')
                {
                    sb = i;
                    eb = j;
                }

                if(ch == 'c')
                {
                    sc = i;
                    ec = j;
                }

                if(ch == 'h')
                {
                    ha = i;
                    hb = j;
                }

                adj[i][j] = ch;
            }
        }

        BFS(ha , hb , row , col);

        maxi = max(maxi , cost[sa][ea]);
        maxi = max(maxi , cost[sb][eb]);
        maxi = max(maxi , cost[sc][ec]);

        pf("Case %d: %d\n", ++tc , maxi);
    }

    return 0;
}

===========================================================================
...................................................................... Another Solution.......................................................

/*
Lionel Messi is such a player that you may catch him, you may touch him, you may feel him
and definitely you may Love him.
Lionel Messi is Messi. A little Magician in this World.

*/

// Algorithm: BFS (3 times)
// Accepted

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 30;

int dir_x[4] = {-1, 1, 0 , 0}, dir_y[4] = {0 , 0 , -1, 1} , n , m;
char adj[high][high];
bool visited[high][high];
int cost[high][high];

void BFS(int x , int y)
{
    int ux , uy , vx , vy , time = 0;

    queue<int>Q;

    visited[x][y] = true;
    cost[x][y] = 0;

    Q.push(x);
    Q.push(y);

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

        uy = Q.front();
        Q.pop();

        for(int i=0; i<4; i++)
        {
            vx = ux + dir_x[i];
            vy = uy + dir_y[i];

            if((vx>=0 && vx<n) && (vy>=0 && vy<m) && (adj[vx][vy] != '#' && adj[vx][vy] != 'm'))
            {
                if(!visited[vx][vy])
                {
                    cost[vx][vy] = cost[ux][uy] + 1;

                    //time += cost[ux][uy] + 1;
                    Q.push(vx);
                    Q.push(vy);
                    visited[vx][vy] = true;
                }

                if(adj[vx][vy]=='h')
                {
                    //time += cost[ux][uy] + 1;
                    cost[vx][vy] = cost[ux][uy] + 1;

                    return;
                }
            }
        }
    }
}

int main()
{
    int test , tc=0 , i , j , sa, ea, sb, eb , sc , ec , t1, t2 , t3 , hx , hy , ans=0;
    char ch;
    sf("%d", &test);
    while(test--)
    {
        sf("%d %d", &n , &m);

        mset(adj, '#');
        mset(visited , false);
        mset(cost , 0);

        t1 = t2 = t3 = ans = 0;

        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                sf(" %c", &ch);

                if(ch == 'a')
                {
                    sa = i;
                    ea = j;
                }

                if(ch == 'b')
                {
                    sb = i;
                    eb = j;
                }

                if(ch == 'c')
                {
                    sc = i;
                    ec = j;
                }

                if(ch == 'h')
                {
                    hx = i;
                    hy = j;
                }

                adj[i][j] = ch;
            }
        }

        BFS(sa , ea);
        //outn(t1);
//        for(i=0; i<n; i++)
//        {
//            for(j=0; j<m; j++)
//            {
//                cout << cost[i][j] << "; ";
//            }
//
//            cout << "\n";
//        }

        //cout << cost[hx][hy] << "\n";

        ans = max(ans , cost[hx][hy]);

        mset(visited , false);
        mset(cost , 0);

        BFS(sb , eb);

        //outn(cost[hx][hy]);

        ans = max(ans , cost[hx][hy]);

        mset(visited , false);
        mset(cost , 0);

        BFS(sc , ec);
        //outn(cost[hx][hy]);

        ans = max(ans , cost[hx][hy]);

        pf("Case %d: %d\n", ++tc , ans);

        //cout << cost[sa][ea] << " " << cost[sb][eb] << " " << cost[sc][ec] << "\n";
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

SPOJ-CMG - Collecting Mango

By -
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<stack> #include<map> #include<cmath> #include<algorithm> #define psb push_back #define ppb pop_back #define all(x) x.begin(),x.end() #define N 1000100 #define sf scanf #define pf printf using namespace std; typedef long long LL; typedef vector<LL>vll; LL ar[N] , num[N]; int main() {     int t , tc=0;     //cin >> t;     sf("%d",&t);     while(t--)     {         LL n, x, arlen=-1, nmlen=-1 , i , maxi=-1 , zar;         char c;         //cin >> n;         sf("%lld",&n);         //cout << "Case " << ++tc << ":\n";         pf("Case %d:\n",++tc);         getchar();         while(n--)         {             //cin >> c;             sf("%c",&c);             if(c == 'A')             {                 //cin >> x;           
Read more

LightOJ 1009 - Back to Underworld

By -
// Accepted /* Analysis: Consider a Graph as 1-2, 2-3, 2-4; if 1 is a vampire than 2 is lykan, as 2 is lykan so 3 and 4 will be vampire. Now total vampires are 3 and lykan is 1, so maximum from this graph is 3. [1=3=4=vampire] another graph is 5-6 and 6-7, 6-8. consider 5 is a vampire so 6 will be lykan. as 6 is lykan than the all adjacent of 6 will be vampire, i mean, 7=8=vampire. Now total vampires are 3 and lykan is 1, so maximum from this graph is 3. And the Answer of this total Graph is 3 + 3 = 6; [As, Graphs are not connected] Decision: If a node is Vampire than all of the adjacent of that node will be Lykan and if a node is Lykan than all of the adjacent of that node will be Vampire, thats why i have represented them as two color black and red. Black means Vampire and Red means Lykan, besides every time i have increased number of vampire and lykans and finally add the maximum as graphs are not connected. */ #include<cstdio> #include<cmath> #include<vector> #in
Read more

LeetCode Palindrome Number

By -
 Problem Description Link:  https://leetcode.com/problems/palindrome-number/ Accepted Solution /* The solution is easy, and I believe everyone knows the process. However, one problem is that x is a number. If it is a string, in that case, we can get the result after reversing it. Therefore, to solve the problem, we have to find the digits by modulating 10, store them in an array, and finally compare from both sides. If we find any discrepancy, we can tell it is not a palindrome. Note that any negative integer would never be a palindrome since it should contain a minus (-) sign. */ class Solution { public:     bool isPalindrome ( int x ) {         int digit [ 50 ], len= 0 ;         bool f = true ;         if (x < 0 ) {             return false ;         }         while (x> 0 )         {             digit [len++] = x% 10 ;             x/= 10 ;         }         for ( int i= 0 , j=len- 1 ; i<len; i++, j--)         {             if ( digit [i] != digit [j])             {  
Read more