Tags » BF's

Light OJ : 1238 - Power Puff Girls

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1238


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long


using namespace std;

const int fx[]={+1,-1,+0,+0};
const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

bool visited;
int d;

void BFS(pii x)
{
    d=0;
    queue<pii>Q;
    visited=0;
    Q.push(x);
    while(!Q.empty())
    {
        pii u=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            pii v;
            v.ff=u.ff+fx[i];
            v.ss=u.ss+fy[i];
            if(!visited)
            {
                visited=1;
                d=d+1;
                Q.push(v);
            }
        }
    }
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t,m,n;
    sf(t);
    TEST_CASE(t)
    {
        sff(m,n);
        ms(visited,0);
        ms(d,0);
        pii a,b,c,h;
        char ch;
       // getchar();
        REP(i,0,m)
            REP(j,0,n)
                {
                    cin>>ch;
                    //getchar();
                    if(ch=='#' || ch=='m')
                        visited[i][j]=1;
                    else if(ch=='h')
                        h.ff=i,h.ss=j;
                    else if(ch=='a')
                        a.ff=i,a.ss=j;
                    else if(ch=='b')
                        b.ff=i,b.ss=j;
                    else if(ch=='c')
                        c.ff=i,c.ss=j;
                }
        BFS(h);
        int ans=d;
        ans=max(ans,d);
        ans=max(ans,d);
        PRINT_CASE;
        pf("%d\n",ans);
    }
    return 0;
} 36 more words
Light OJ

CodeFu 2015: Round 1

Изминатиот викенд се одржа првата рунда од квалификациите за годишниот CodeFu натпревар. Доста интересен натпревар со не многу тешки задачи, кој имаше 90 учесника (повеќето студенти, но исто така и по некој средношколец). 806 more words

Ad Hoc

Light OJ 1174 - Commandos

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1174



/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             110
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

int n,m,a,b,u,v;
vector<int>edge;
bool visited;
int distance1;
int distance2;

void BFS(int src,int d[])
{
    queue<int>Q;
    d=0;
    Q.push(src);
    ms(visited,0);
    visited=1;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        REP(i,0,SZ(edge[u]))
        {
            int v=edge[u][i];
            if(visited[v]==0)
            {
                visited[v]=1;
                Q.push(v);
                d[v]=d[u]+1;
            }
        }
    }
}

void clr()
{
    REP(i,0,n)
    {
        edge[i].clear();
    }
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        sff(n,m);
        REP(i,0,m)
        {
            sff(u,v);
            edge[u].pb(v);
            edge[v].pb(u);
        }
        sff(a,b);
        ms(distance1,0);
        ms(distance2,0);
        BFS(a,distance1);
        BFS(b,distance2);
        int ans=-1;
        REP(i,0,n)
        {
            ans=max(ans,distance1[i]+distance2[i]);
        }
        PRINT_CASE;
        pf("%d\n",ans);
        clr();
    }
    return 0;
} 6 more words
Light OJ

1049 - One Way Roads

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1049


#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d%d",&a,&b)
#define siii(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

bool left_pos,right_pos;

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    si(t);
    TEST_CASE(t)
    {
        int n,a,b,c;
        int left_cost=0,rigt_cost=0;
        si(n);
        ms(left_pos,0);
        ms(right_pos,0);
        loop(i,n)
        {
            siii(a,b,c);
            if(left_pos[a]==0 && right_pos[b]==0)
            {
                left_pos[a]=right_pos[b]=1;
                left_cost+=c;
            }
            else
            {
                right_pos[a]=left_pos[b]=1;
                rigt_cost+=c;
            }
        }
        PRINT_CASE;
        pf("%d\n",min(left_cost,rigt_cost));
    }

    return 0;
}

Light OJ

#BFS: M.S. In Conclusion...

I suck.

Just Kidding. But it wasn’t my best race. It was my worst, actually (I think. Maybe my first ever half was about the same time, but I was on a high for completing my first ever half that it didn’t matter). 416 more words

Weiler Packaged and Ready to Go!

Our Weiler 603 Blow Fill Seal Machine was crated right here in our SSLLC Facility. Watch as the process unfolds!

Used Equipment

(LightOj) 1141 - Number Transformation


/****************************************************************
   ▄█    █▄       ▄████████    ▄████████  ▄█  ▀█████████▄
  ███    ███     ███    ███   ███    ███ ███    ███    ███
  ███    ███     ███    ███   ███    █▀  ███   ███    ███
 ▄███▄▄▄▄███▄▄   ███    ███   ███        ███  ▄███▄▄▄██▀
▀▀███▀▀▀▀███▀  ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄
  ███    ███     ███    ███          ███ ███    ███    ██▄
  ███    ███     ███    ███    ▄█    ███ ███    ███    ███
  ███    █▀      ███    █▀   ▄████████▀  █▀   ▄█████████▀
****************************************************************/



#include<bits/stdc++.h>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)

#define take(args...) asdf,args
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define debug(args...) cerr,args; cerr<<endl;
using namespace std;


template<typename T>
ostream& operator<<(ostream& output, vector<T>&v)
{
    output<<"[ ";
    if(SZ(v))
    {
        output<<v[0];
    }
    FOR(i, 1, SZ(v))
    {
        output<<", "<<v[i];
    }
    output<<" ]";
    return output;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& output, pair<T1, T2>&p)
{
    output<<"( "<<p.fr<<", "<<p.sc<<" )";
    return output;
}




template<typename T>
ostream& operator,(ostream& output, T x)
{
    output<<x<<" ";
    return output;
}



struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;



//Header ends here



#define MAXX 1007

vector<int>factors;

vector<int>primes;

void generatePrimes()
{
    bool isPrime;

    mem(isPrime, 1);

    int root = sqrt(MAXX) + 7;

    for(int i=3; i<root; i++)
    {
        if(isPrime[i])
        {
            for(int j=i*i; j<MAXX; j+=(2*i))
            {
                isPrime[j] = false;
            }
        }
    }

    for(int i=2; i<MAXX;)
    {
        if(isPrime[i])
        {
            for(int j=2; i*j < MAXX; j++)
            {
                factors.pb(i);
            }
        }

        if(i == 2)
        {
            i++;
        }
        else
        {
            i += 2;
        }
    }
}


void init()
{
    generatePrimes();
}




int bfs(int source, int target)
{
    bool visited;

    int dist;

    mem(dist, -1);

    mem(visited, 0);


    queue<int>Q;

    Q.push(source);

    visited1 = true;
    dist1 = 0;

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

        loop(i, SZ(factors[u]))
        {
            int v = u + factors[u][i];

            if( (v <= target) && !visited[v] )
            {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                if(v == target)
                {
                    break;
                }
                Q.push(v);
            }
        }
    }

    return dist;
}


int main()
{
    init();


    int kases, kaseno = 0;

    int s, t;

    sf("%d", &kases);

    while(kases--)
    {
        sf("%d %d", &s, &t);
        pf("Case %d: %d\n", ++kaseno, bfs(s, t));
    }

    return 0;
} 7 more words
Graph