UVa 657 - The die is cast

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[4]={1,0,-1,0};
ll y[4]={0,1,0,-1};
ll g[60][60];
bool visited[60][60];
ll w,h;
ll ct,id;
struct s
{
    ll px,py;
}tmp[1000];
void dfs(ll,ll);
void dfs1(ll,ll);
void dfs1(ll p,ll q)
{
    //cout<<p<<" "<<q<<" \n";
    visited[p][q]=1;
    for(ll i=0;i<4;i++)
    {
        ll u,v;
        u=p+x[i];
        v=q+y[i];
        if(g[u][v]==1&&visited[u][v]==0&&u>=0&&v>=0&&u<h&&v<w)
        {
            //cout<<p<<" "<<q<<" "<<u<<" "<<v<<endl;
            dfs1(u,v);
        }
        if(g[u][v]==0&&visited[u][v]==0&&u>=0&&v>=0&&u<h&&v<w)
        {
            //cout<<u<<" "<<v<<endl;
            //dfs(u,v);
            tmp[id].px=u;
            tmp[id].py=v;
            id++;
        }
    }
    return;
}
void dfs(ll xx,ll yy)
{
    //cout<<xx<<" "<<yy<<endl;
    ll u,v,i;
    if(!visited[xx][yy]&&g[xx][yy]==1)
    {
        visited[xx][yy]=1;
        //cout<<xx<<"="<<yy<<endl;
        ct++;
        for(i=0;i<4;i++)
        {
            u=xx+x[i];
            v=yy+y[i];
            if(u>=0&&v>=0&&u<h&&v<w&&!visited[u][v]&&g[u][v]!=-1)
            {
                if(g[u][v]==1)
                {
                    dfs1(u,v);
                }
                if(g[u][v]==0)
                {
                    dfs(u,v);
                }
            }
        }
    }
    if(!visited[xx][yy]&&g[xx][yy]==0)
    {
        //cout<<xx<<"----"<<yy<<endl;
        visited[xx][yy]=1;
        for(i=0;i<4;i++)
        {
            u=xx+x[i];
            v=yy+y[i];
            if(u>=0&&v>=0&&u<h&&v<w&&!visited[u][v]&&g[u][v]!=-1)
            {
                if(g[u][v]==1)
                {
                    //cout<<u<<"-"<<v<<endl;
                    ct++;
                    dfs1(u,v);
                }
                if(g[u][v]==0)
                {
                    dfs(u,v);
                }
            }
        }
    }
    //cout<<"ct::"<<ct<<endl;
    return;
}
int main()
{
    //ofstream o("op.txt");
    ll i,j,k,l,m,n,cnt=1;
    while(cin>>w>>h)
    {
        ll res;
        if(w==0&&h==0)
            break;
        memset(g,0,sizeof(g));
        memset(visited,0,sizeof(visited));
        vector<ll>v;
        for(i=0;i<h;i++)
        {
            for(j=0;j<w;j++)
            {
                char c;
                cin>>c;
                if(c=='.')
                {
                    g[i][j]=-1;
                }
                if(c=='X')
                {
                    g[i][j]=1;
                }
            }
        }
        for(i=0;i<h;i++)
        {
            for(j=0;j<w;j++)
            {
                if(visited[i][j]==0&&g[i][j]!=-1)
                {
                    //cout<<i<<"==="<<j<<endl;
                    ct=0;
                    id=0;
                    dfs(i,j);
                    for(k=0;k<id;k++)
                    {
                        dfs(tmp[k].px,tmp[k].py);
                    }
                    //cout<<"CT:"<<ct<<endl;
                    v.push_back(ct);
                }
            }
        }
        printf("Throw %lld\n",cnt);
        //o<<"Throw "<<cnt<<endl;
        sort(v.begin(),v.end());
        for(i=0;i<v.size();i++)
        {
            printf("%lld",v[i]);
            //o<<v[i];
            if(i!=v.size()-1)
            {
                //o<<" ";
                printf(" ");
            }
        }
        //o<<endl<<endl;
        cnt++;
        printf("\n\n");
    }
    return 0;
}

Light OJ 1174 - Commandos

#include<bits/stdc++.h>
#define mx 109
#define inf 1e8
#define nil -999999999
using namespace std;
typedef long long ll;
ll graph[mx][mx];
ll path[mx][mx];
ll edge,node,idx;
void initialize_path()
{
    ll i,j,k,l,m,n;
    for(i=0;i<mx;i++)
    {
        for(j=0;j<=mx;j++)
        {
            if(graph[i][j]==inf)
            {
                path[i][j]=nil;
            }
            else
            {
                path[i][j]=i;
            }
        }
    }
    return;
}
void solve()
{
    ll i,j,k,l,m,n;
    cin>>node>>edge;
    for(i=0;i<mx;i++)
    {
        for(j=0;j<mx;j++)
        {
            graph[i][j]=inf;
        }
    }
    for(i=0;i<=edge;i++)
    {
        graph[i][i]=0;
    }
    for(i=0;i<mx;i++)
    {
        for(j=0;j<mx;j++)
        {
            if(i==j)
            {
                graph[i][j]=0;
                continue;
            }
            graph[i][j]=inf;
        }
    }
    for(i=1;i<=edge;i++)
    {
        ll a,b,cost;
        cin>>a>>b;
        cost=1;
        graph[a][b]=cost;
        graph[b][a]=cost;
    }
    for(k=0;k<node;k++)
    {
        for(i=0;i<node;i++)
        {
            for(j=0;j<node;j++)
            {
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    ll st,ed;
    cin>>st>>ed;
    ll mxx=-9999;
    for(i=0;i<node;i++)
    {
        ll tmp=graph[i][st]+graph[i][ed];
        if(tmp>mxx)
        {
            mxx=tmp;
        }
    }
    cout<<"Case "<<idx<<": "<<mxx<<endl;
    idx++;
    return;
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    idx=1;
    for(k=1;k<=test;k++)
    {
        solve();
    }
    return 0;
}

UVa 10000 - Longest Paths

#include<bits/stdc++.h>
#define mx 109
#define inf 1e8
#define nil -999999999
using namespace std;
typedef long long ll;
ll graph[mx][mx];
ll path[mx][mx];
ll edge,node;
int main()
{
    //ofstream o("op.txt");
    ll i,j,k,l,m,n,idx;
    idx=1;
    while(1)
    {
        cin>>node;
        if(node==0)
            break;
        ll start;
        cin>>start;
        for(i=0;i<mx;i++)
        {
            for(j=0;j<mx;j++)
            {
                graph[i][j]=nil;
            }
        }
        for(i=1;i<=mx;i++)
        {
            graph[i][i]=0;
        }
        for(i=1;;i++)
        {
            ll a,b,cost;
            cin>>a>>b;
            if(a==0&&b==0)
                break;
            graph[a][b]=1;
        }
        for(k=1;k<=node;k++)
        {
            for(i=1;i<=node;i++)
            {
                for(j=1;j<=node;j++)
                {
                    graph[i][j]=max(graph[i][j],graph[i][k]+graph[k][j]);
                }
            }
        }
        ll dis,nde;
        dis=-999;
        for(i=1;i<=node;i++)
        {
            if(graph[start][i]>dis)
            {
                nde=i;
                dis=graph[start][i];
            }
        }
        cout<<"Case "<<idx<<": The longest path from "<<start<<" has length "<<dis<<", finishing at "<<nde<<"."<<endl<<endl;
        idx++;
    }
    return 0;
}

SPOJ CRSCNTRY - Cross-country

#include<bits/stdc++.h>
#define MAXC 5000
using namespace std;
typedef long long ll;
ll A[MAXC],B[MAXC];
ll lenA,lenB;
ll dp[MAXC][MAXC];
bool visited[MAXC][MAXC];
ll calcLCS(ll i,ll j)
{
if(A[i]==0||B[j]==0)
        return 0;
if(visited[i][j])
        return dp[i][j];
ll ans=0;
if(A[i]==B[j])
        ans=1+calcLCS(i+1,j+1);
else
{
ll val1=calcLCS(i+1,j);
ll val2=calcLCS(i,j+1);
ans=max(val1,val2);
}
visited[i][j]=1;
dp[i][j]=ans;
return dp[i][j];
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
{
   ll lenA=0;
   while(1)
        {
            cin>>A[lenA];
            lenA++;
            if(A[lenA-1]==0)
            {
                break;
            }
        }
        ll mx=-999999999;
        lenB=0;
        while(1)
        {
            cin>>B[lenB];
            if(lenB==0&&B[lenB]==0)
            {
                break;
            }
            else
            {
                lenB++;
                if(B[lenB-1]==0)
                {
                    memset(visited,0,sizeof(visited));
                    mx=max(mx,calcLCS(0,0));
                    lenB=0;
                }
            }
        }
        cout<<mx<<endl;
}
return 0;
}

SPOJ BYTESM2 - Philosophers Stone

#include<bits/stdc++.h>
#define inf 99999999999
using namespace std;
typedef long long ll;
ll arr[109][109];
ll dp[1009][109];
ll row,col;
ll solve(ll i,ll j)
{
    if (i>=0&&i<row&&j>=0&&j<col)
    {
        if (dp[i][j]!=-1)
            return dp[i][j];
        ll ret=-inf;
        ret=max(ret,solve(i+1,j)+arr[i][j]);
        ret=max(ret,solve(i+1,j-1)+arr[i][j]);
        ret=max(ret,solve(i+1,j+1)+arr[i][j]);
        return dp[i][j]=ret;
    }
    else
        return 0;
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>row>>col;
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            {
                cin>>arr[i][j];
            }
        }
        ll mx=-99999999;
        for(i=0;i<col;i++)
        {
            memset(dp,-1,sizeof(dp));
            mx=max(mx,solve(0,i));
        }
        cout<<mx<<endl;
    }
    return 0;
}

SPOJ CPCRC1C - Sum of Digits

//To understand the proceedings please visit http://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sumOfDigitsFrom1ToN(ll n)
{
    if (n<10)
      return n*(n+1)/2;
    ll d=log10(n);
    ll *a=new ll[d+1];
    a[0]=0,a[1]=45;
    for (ll i=2;i<=d;i++)
        a[i]=a[i-1]*10+45*ceil(pow(10,i-1));
    ll p=ceil(pow(10,d));
    int msd = n/p;
    return msd*a[d]+(msd*(msd-1)/2)*p+
           msd*(1+n%p)+sumOfDigitsFrom1ToN(n%p);
}
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n>>m)
    {
        if(n==-1&&m==-1)
            break;
        else
        {
            ll ans=sumOfDigitsFrom1ToN(max(n,m))-sumOfDigitsFrom1ToN(min(n,m)-1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

SPOJ COINS - Bytelandian gold coins

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll n;
ll solve(ll n)
{
    if(n==0)
        return 0;
    else
    {
        if(mp[n])
            return mp[n];
        else
        {
            ll t=max(n,solve(n/2)+solve(n/3)+solve(n/4));
            mp[n]=t;
            return mp[n];
        }
    }
}
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n)
    {
        mp.clear();
        cout<<solve(n)<<endl;
    }
    return 0;
}

SPOJ ANARC09A - Seinfeld

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n;
    string s;
    k=1;
    while(1)
    {
        cin>>s;
        if(s[0]=='-')
            break;
        else
        {
            stack<char>st;
            for(i=0;i<s.size();i++)
            {
                if(st.empty())
                {
                    st.push(s[i]);
                    continue;
                }
                if(st.top()=='{'&&s[i]=='}')
                {
                    st.pop();
                    continue;
                }
                else
                {
                    st.push(s[i]);
                }
            }
            ll cnt1=0;
            ll cnt2=0;
            while(!st.empty())
            {
                if(st.top()=='{')
                {
                    cnt1++;
                }
                else
                {
                    cnt2++;
                }
                st.pop();
            }
            ll cnt;
            if(cnt1%2==0)
            {
                cnt1/=2;
            }
            else
            {
                cnt1=(cnt1/2)+1;
            }
            if(cnt2%2==0)
            {
                cnt2/=2;
            }
            else
            {
                cnt2=(cnt2/2)+1;
            }
            cnt=cnt1+cnt2;
            cout<<k<<". "<<cnt<<endl;
            k++;
        }
    }
    return 0;
}

SPOJ AIBOHP - Aibohphobia

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[6109][6109];
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        string s1,s2;
        cin>>s1;
        s2=s1;
        reverse(s2.begin(),s2.end());
        memset(dp,0,sizeof(dp));
        for(i=s1.size()-1;i>=0;i--)
        {
            for(j=s2.size()-1;j>=0;j--)
            {
                if(s1[i]==s2[j])
                {
                    dp[i][j]=1+dp[i+1][j+1];
                }
                else
                {
                    dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        cout<<s1.size()-dp[0][0]<<endl;
    }
    return 0;
}

SPOJ ANARC08E - Relax! It is just a game

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n;
    while(1)
    {
        cin>>n>>m;
        if(n==-1&&m==-1)
        {
            break;
        }
        else
        {
            if(n==0&&m==0)
            {
                cout<<"0+0!=0"<<endl;
                continue;
            }
            if(n==1||m==1)
            {
                cout<<n<<"+"<<m<<"="<<n+m<<endl;
            }
            else
            {
                cout<<n<<"+"<<m<<"!="<<n+m<<endl;
            }
        }
    }
}

Light OJ 1148 Mad Counting

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        map<ll,ll>mp;
        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>m;
            mp[m]++;
        }
        ll cnt=0;
        map<ll,ll>::iterator it;
        for(it=mp.begin();it!=mp.end();++it)
        {
            ll p=it->first;
            ll q=it->second;
            p++;
            if(q%p==0)
            {
                cnt+=(((q/p)*(p)));
            }
            else
            {
                cnt+=((q/p)*(p)+p);
            }
        }
        cout<<"Case "<<k<<": "<<cnt<<endl;
    }
    return 0;
}

Light Oj 1078 Integer Divisibility

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll divisor;
ll rem;
ll mod_chk(ll i)
{
    rem=(rem*10+s[i]-'0')%divisor;
    return rem;
}
int main()
{
    ll i,j,k,l,m,n,test;
    scanf("%lld",&test);
    for(k=1;k<=test;k++)
    {
        char c;
        scanf("%lld %c",&divisor,&c);
        s="";
        ll cnt=1;
        s+=c;
        ll in=0;
        rem=0;
        while(mod_chk(in)!=0)
        {
            s+=c;
            cnt++;
            in++;
        }
        printf("Case %lld: %lld\n",k,cnt);
    }
    return 0;
}

UVa 352 - The Seasonal War

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt;
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
ll g[1000][1000];
bool visited[1009][1009];
ll n;
void dfs(ll i,ll j)
{
    visited[i][j]=1;
    for(ll m=0;m<8;m++)
    {
        ll p=i+dx[m];
        ll q=j+dy[m];
        if(p>=0&&p<n&&q>=0&&q<n&&visited[p][q]==0&&g[p][q]==1)
        {
            dfs(p,q);
        }
    }
    return;
}
int main()
{
    ll i,j,k=1,l,m;
    while(cin>>n)
    {
        memset(g,0,sizeof(g));
        memset(visited,0,sizeof(visited));
        for(i=0;i<n;i++)
        {
            string s;
            cin>>s;
            for(j=0;j<s.size();j++)
            {
                if(s[j]=='0')
                {
                    g[i][j]=0;
                }
                else
                {
                    g[i][j]=1;
                }
            }
        }
        cnt=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(visited[i][j]==0&&g[i][j]==1)
                {
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        cout<<"Image number "<<k<<" contains "<<cnt<<" war eagles."<<endl;
        k++;
    }
    return 0;
}

Light OJ 1164 Horrible Queries

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
typedef long long ll;
struct s
{
    ll sum,prop;
}tree[4*mx];
ll arr[100009];
void init(int node,int b,int e)
{
    if (b==e)
    {
        tree[node].sum=arr[b];
        tree[node].prop=0;
        return;
    }
    int Left=node*2;
    int Right=(node*2)+1;
    int mid=(b+e)/2;
    init(Left,b,mid);
    init(Right,mid+1,e);
    tree[node].sum=tree[Left].sum + tree[Right].sum;
    tree[node].prop=0;
}
void update(int node,int b,int e,int i,int j,ll x)
{
    if(i>e||j<b)
        return;
    if(b>=i&&e<=j)
    {
        tree[node].prop+=x;
        tree[node].sum+=(e-b+1)*x;
        return;
    }
    ll Left=node*2;
    ll Right=(node*2)+1;
    ll mid=(b+e)/2;
    update(Left,b,mid,i,j,x);
    update(Right,mid+1,e,i,j,x);
    tree[node].sum=tree[Left].sum+tree[Right].sum+(e-b+1)*tree[node].prop;
}
ll query(int node,int b,int e,int i,int j,ll carry=0)
{
    if(i>e||j<b)
        return 0;
    if (b>=i&&e<=j)
    {
        return tree[node].sum+carry*(e-b+1);
    }
    int Left=node<<1;
    int Right=(node<<1)+1;
    int mid=(b+e)>>1;
    ll p1=query(Left,b,mid,i,j,carry+tree[node].prop);
    ll p2=query(Right,mid+1,e,i,j,carry+tree[node].prop);
    return p1+p2;
}
int main()
{
    int i,j,k,l,m,n,test;
    scanf("%lld",&test);
    for(m=1;m<=test;m++)
    {
        scanf("%d%d",&n,&k);
        printf("Case %d:\n",m);
        memset(arr,0,sizeof(arr));
        init(1,1,n);
        for(i=0;i<k;i++)
        {
            int op;
            scanf("%d",&op);
            if(op==0)
            {
                int st,ed,vl;
                scanf("%d%d%lld",&st,&ed,&vl);
                update(1,1,n,st+1,ed+1,vl);
            }
            if(op==1)
            {
                int st,ed;
                scanf("%d%d",&st,&ed);
                ll y=query(1,1,n,st+1,ed+1);
                printf("%lld\n",y);
            }
        }
    }
    return 0;
}

Light OJ 1025 - The Specials Menu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[100];
ll dp[100][100];
ll l,n;
string s;
ll solve(ll i,ll j)
{
    if(i>j)
        return 0;
    if(i==j)
        return 1;
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(s[i]==s[j])
    {
        dp[i][j]=1+solve(i+1,j)+solve(i,j-1);
    }
    if(s[i]!=s[j])
    {
        dp[i][j]=solve(i+1,j)+solve(i,j-1)-solve(i+1,j-1);
    }
    return dp[i][j];
}
int main()
{
    ll i,j,k,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>s;
        memset(dp,-1,sizeof(dp));
        l=s.size();
        cout<<"Case "<<k<<": "<<solve(0,l-1)<<endl;
    }
    return 0;
}

BFS in a 3D grid

#include<bits/stdc++.h>
using namespace std;
int graph[35][35][35];
int visited[35][35][35];
int level[35][35][35];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int main()
{
    int r,c,w;
    cin>>w>>r>>c;//w:how many levels,c:row in each level,c:column in each level
    memset(graph,0,sizeof(graph));
    for(int i=0;i<w;i++)
    {
        for(int j=0;j<r;j++)
        {
            for(int k=0;k<c;k++)
            {
                cin>>graph[i][j][k];//use 1 and 0 as input
            }
        }
    }
    memset(visited,0,sizeof(visited));
    memset(level,0,sizeof(level));
    queue<int>q;
    int stx,sty,stz,enx,eny,enz;
    cin>>stx>>sty>>stz;
    cin>>enx>>eny>>enz;
    visited[stx][sty][stz]=true;
    level[stx][sty][stz]=0;
    q.push(stx);
    q.push(sty);
    q.push(stz);
    int ans;
    bool flag=0;
    while(!q.empty())
    {
        int f1,f2,f3;
        f1=q.front();
        q.pop();
        f2=q.front();
        q.pop();
        f3=q.front();
        q.pop();
        for(int in=0;in<6;in++)
        {
            int v1,v2,v3;
            v1=f1+x[in];
            v2=f2+y[in];
            v3=f3+z[in];
            if(!visited[v1][v2][v3]&&!level[v1][v2][v3]&&graph[v1][v2][v3]==1&&(v1>=0&&v1<w&&v2>=0&&v2<r&&v3>=0&&v3<c))
            {
                {
                    level[v1][v2][v3]=level[f1][f2][f3]+1;
                    //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                    if(v1==enx&&v2==eny&&v3==enz)
                    {
                        flag=1;
                        ans=level[v1][v2][v3];
                    }
                    q.push(v1);
                    q.push(v2);
                    q.push(v3);
                    visited[v1][v2][v3]=true;
                }
            }
        }
    }
    if(flag)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

UVa 532 - Dungeon Master

#include<bits/stdc++.h>
using namespace std;
int graph[35][35][35];
int visited[35][35][35];
int level[35][35][35];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int main()
{
    int r,c,w,i,j,k;
    while(1)
    {
        cin>>w>>r>>c;
        if(w==0&&r==0&&c==0)
            break;
        int stx,sty,stz,enx,eny,enz;
        memset(graph,0,sizeof(graph));
        for(i=0;i<w;i++)
        {
            for(j=0;j<r;j++)
            {
                for(k=0;k<c;k++)
                {
                    char c;
                    cin>>c;
                    if(c=='S')
                    {
                        stx=i;
                        sty=j;
                        stz=k;
                        graph[i][j][k]=1;
                        continue;
                    }
                    if(c=='E')
                    {
                        enx=i;
                        eny=j;
                        enz=k;
                        graph[i][j][k]=1;
                    }
                    if(c=='.')
                        graph[i][j][k]=1;
                    if(c=='#')
                        graph[i][j][k]=0;
                }
            }
        }
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        visited[stx][sty][stz]=true;
        level[stx][sty][stz]=0;
        q.push(stx);
        q.push(sty);
        q.push(stz);
        int ans;
        bool flag=0;
        while(!q.empty())
        {
            int f1,f2,f3;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            f3=q.front();
            q.pop();
            for(int in=0;in<6;in++)
            {
                int v1,v2,v3;
                v1=f1+x[in];
                v2=f2+y[in];
                v3=f3+z[in];
                if(!visited[v1][v2][v3]&&!level[v1][v2][v3]&&graph[v1][v2][v3]==1&&(v1>=0&&v1<w&&v2>=0&&v2<r&&v3>=0&&v3<c))
                {
                    {
                        level[v1][v2][v3]=level[f1][f2][f3]+1;
                        //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                        if(v1==enx&&v2==eny&&v3==enz)
                        {
                            flag=1;
                            ans=level[v1][v2][v3];
                        }
                        q.push(v1);
                        q.push(v2);
                        q.push(v3);
                        visited[v1][v2][v3]=true;
                    }
                }
            }
        }
        if(flag)
        {
            if(ans<2)
            {
                cout<<"Escaped in "<<ans<<" minute."<<endl;
            }
            else
            {
                cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
            }
        }
        else
            cout<<"Trapped!"<<endl;
    }
    return 0;
}

Light OJ 1021 Painful Bases

#include<bits/stdc++.h>
#define mxn 20
using namespace std;
typedef long long ll;
ll n,arr[50],b,k;
string s;
ll dp[25][1<<17];
ll Set(ll N,ll pos){return N=N | (1<<pos);}
ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
bool check(ll N,ll pos){return (bool)(N & (1<<pos));}
ll solve(ll value,ll mask)
{
    if(mask==(1<<n)-1)
    {
        if(value==0)
            return 1;
        else
            return 0;
    }
    if(dp[value][mask]!=-1)
    {
        return dp[value][mask];
    }
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        if(check(mask,i)==0)
        {
            ans+=solve((value*b+s[i])%k,Set(mask,i));
        }
    }
    return dp[value][mask]=ans;
}
int main()
{
    ll i,j,l,m,test;
    cin>>test;
    for(l=1;l<=test;l++)
    {
        cin>>b>>k;
        cin>>s;
        memset(dp,-1,sizeof(dp));
        n=s.size();
        for(i=0;i<n;i++)
        {
            if(s[i]>='0'&&s[i]<='9')
            {
                s[i]=s[i]-'0';
            }
            else
            {
                s[i]=s[i]-'A'+10;
            }
        }
        cout<<"Case "<<l<<": "<<solve(0,0)<<endl;
    }
    return 0;
}

Light OJ 1017 Brush (III)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll arr[1009],dp[1009][1009];

ll n,l;

ll solve(ll pos,ll lft)

{

    ll i;

    if(pos>=n||lft<=0)

        return 0;

    if(dp[pos][lft]!=-1)

        return dp[pos][lft];

    ll bnd=arr[pos]+l;

    ll cnt=0;

    for(i=pos;i<n;i++)

    {

        if(arr[i]<=bnd)

        {

            cnt++;

        }

        else

        {

            break;

        }

    }

    return dp[pos][lft]=max(cnt+solve(i,lft-1),solve(pos+1,lft));

}

int main()

{

    ll i,j,k,m,test,x;

    cin>>test;

    for(k=1;k<=test;k++)

    {

        memset(dp,-1,sizeof(dp));

        cin>>n>>l>>m;

        for(i=0;i<n;i++)

        {

            cin>>x>>arr[i];

        }

        sort(arr,arr+n);

        cout<<"Case "<<k<<": "<<solve(0,m)<<endl;

    }

}