UVA :336-A Node Too Far

#include <bits/stdc++.h>
#define READ freopen("input.txt","r",stdin);
#define WRITE freopen("output.txt","w",stdout);
using namespace std;

void BFS(int a);

map<int,int>color;
map<int,int>cost;
map<int,int>no_of_node;
map<int,int>::iterator it;
vector<int>v[100000];
int row,col;
queue<int>Q;

int x[]= {-1,+0,+1,+0};
int y[]= {+0,-1,+0,+1};

int main()
{
    //READ WRITE
    int edge,cas=0;
    while(scanf("%d",&edge)==1&&edge!=0)
    {
        color.clear();
        cost.clear();
        no_of_node.clear();
        for(int i=0;i<100000;i++) v[i].clear();
        for(int a=0; a<edge; a++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
            no_of_node[x]++;
            no_of_node[y]++;

        }


        int node,dis;
        while(scanf("%d %d",&node,&dis)==2)
        {
            if(node==0&&dis==0) break;
            color.clear();
            cost.clear();
            int c=0;


            BFS(node);

            for( it=cost.begin(); it!=cost.end(); it++)
            {

                if(it->second>dis) c++;
            }
            c+=no_of_node.size()-color.size();
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cas,c,node,dis);

        }


    }

    return 0;
}

void BFS(int root)
{
    color[root]=1;
    cost[root]=0;
    Q.push(root);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            int num=v[u][i];
            if(color[num]==0)
            {

                cost[num]=cost[u]+1;
                color[num]=1;
                Q.push(num);
            }

        }

    }

}

UVA solution: 10611 - The Playboy Chimp

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ary[50005],temp[50005],q;
    int n;
    scanf("%d",&n);

    for(int i=0; i<n; i++)scanf("%d",&ary[i]);
    int len=0;

    for(int i=0; i<n; i++)
    {
        if(i==0) temp[len++]=ary[i];

        else
        {
            if (ary[i]!=ary[i-1])  temp[len++]=ary[i];
        }

    }
    cin>>q;
   //for(int i=0; i<len; i++) cout<<temp[i]<<endl;
    for(int i=0; i<q; i++)
    {
        int target;
        scanf("%d",&target);
        if(target<temp[0])
        {
            printf("X %d\n",temp[0]);
            continue;
        }
        if(target==temp[0])
        {
            printf("X %d\n",temp[1]);
            continue;
        }
        if(target==temp[len-1])
        {
            printf("%d X\n",temp[len-2]);
            continue;
        }
        if(target>temp[len-1])
        {
            printf("%d X\n",temp[len-1]);
            continue;
        }
        int low=0,high=len-1,mid;

        while(high-low!=1)
        {
            mid=(low+high)/2;

            if(target==temp[mid])
            {

                low=mid-1;
                high=mid+1;
                break;
            }
            else if(target>temp[mid])low=mid;
            else high=mid;

        }
        printf("%d %d\n",temp[low],temp[high]);

    }





    return 0;
}

uva 439 - Knight Moves solution

#include<bits/stdc++.h>
using namespace std;
void BFS(int a,int b);
int cost[100][100];
int check[100][100];
queue<int>Q;
int dr[]= {-2,-2,+2,+2,+1,-1,+1,-1};
int dc[]= {+1,-1,+1,-1,-2,-2,+2,+2};
int start_row, start_col,  end_row, end_col;
int main()
{
    string a,b;
    while(cin>>a>>b)
    {
        start_row=int(a[0]-96);
        start_col=a[1]-'0';
        end_row=int(b[0]-96);
        end_col=b[1]-'0';
        // cout<<start_row<<end_row<<endl;
        memset(cost,0,sizeof(cost));
        memset(check,0,sizeof(check));
        BFS(start_row-1,start_col-1);
        cout<<"To get from "<<a<<" to "<<b<<" takes "<<cost[end_row-1][end_col-1]<<" knight moves."<<endl;

    }

    return 0;
}
void BFS(int r,int c)
{
    check[r][c]=1;
    cost[r][c]=0;
    Q.push(r);
    Q.push(c);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        int v=Q.front();
        Q.pop();
        for(int i=0; i<8; i++)
        {
            int row=dr[i]+u;
            int col=dc[i]+v;
            if(((row>=0&&row<8)&&(col>=0&&col<8))&&check[row][col]==0)
            {
                check[row][col]=1;
                cost[row][col]=cost[u][v]+1;
                Q.push(row);
                Q.push(col);
            }
        }


    }



}

UVA :10653 - Bombs! NO they are Mines!! solution

#include <bits/stdc++.h>

using namespace std;

void BFS(int a,int b);
queue<pair<int,int> >Q;

int adj[1001][1001];
int check[1001][1001];
int cost[1001][1001];

int dr[]= {-1,+0,+1,+0};
int dc[]= {+0,-1,+0,+1};

int start_x,start_y,end_x,end_y;
int row,col;

int main()
{

    while(scanf("%d %d",&row,&col)==2)
    {
        if(row==0&&col==0) break;

        memset(adj,0,sizeof(adj));
        memset(check,0,sizeof(check));
        memset(cost,0,sizeof(cost));
        int edge;
        scanf("%d",&edge);
        for(int i=0; i<edge; i++)
        {
            int r,bomb;
            scanf("%d %d",&r,&bomb);
            while(bomb--)
            {
                int c;
                scanf("%d",&c);
                adj[r][c]=1;

            }

        }


        scanf("%d %d %d %d",&start_x,&start_y,&end_x,&end_y);
        BFS(start_x,start_y);
        cout<<cost[end_x][end_y]<<endl;

    }


    return 0;
}

void BFS(int x,int y)
{
    check[x][y]=1;
    cost[x][y]=0;
    Q.push(make_pair(x,y));

    while(!Q.empty())
    {
        pair<int,int> top=Q.front();
        Q.pop();
        for(int i=0; i<4; i++)
        {
            int tx=top.first+dr[i];
            int ty=top.second+dc[i];

            if(((tx>=0&&tx<row)&&(ty>=0&ty<col))&&adj[tx][ty]==0)
            {
                if(check[tx][ty]==0)
                {
                    check[tx][ty]=1;
                    adj[tx][ty]=1;
                    cost[tx][ty]=cost[top.first][top.second]+1;
                   // cout<<tx<<ty<<endl;
                    Q.push(make_pair(tx,ty));
                }

            }

        }

    }

}

UVA :1230 - MODEX solution

#include <bits/stdc++.h>
#define sc scanf
#define pf printf
using namespace std;

typedef long long ll;

ll bigmod(ll base,ll pow,ll mod)
{
    if(pow==0) return 1;
    if(pow&1)
    {

        ll ret=(bigmod(base,pow-1,mod))%mod;
        return  (ret*base)%mod;

    }
    else
    {
        ll ret=(bigmod(base,pow/2,mod))%mod;
        return (ret*ret)%mod;
    }

}

int main()
{

    ll base,pow,mod;
    int n;
    while(sc("%d",&n)==1)
    {
        if(n==0) break;
        int t=n;
        while(t--)
        {
            cin>>base>>pow>>mod;
            cout<<bigmod(base,pow,mod)<<endl;
        }
    }


    return 0;
}

uva: 352 - The Seasonal War solution

#include <bits/stdc++.h>
#define sc scanf
#define pf printf
typedef long long ll;
using namespace std;


void dfs(int i,int j);
vector<string>v;
int n,cas=0;
bool check[101][101];

int x[]= {-1,-1,-1,0,0,1,1,1};
int y[]= {-1,0,1,-1,1,-1,0,1};

int main()
{
    while(sc("%d",&n)==1)
    {
        v.clear();
        memset(check,0,sizeof(check));
        for(int i=0; i<n; i++)
        {
            string s;
            cin>>s;
            v.push_back(s);
        }
        int cn=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(check[i][j]==0)
                {
                    check[i][j]=1;
                    if(v[i][j]=='1')
                    {
                        cn++;
                        dfs(i,j);
                    }

                }
            }
        }
        pf("Image number %d contains %d war eagles.\n",++cas,cn);

    }

    return 0;
}

void dfs(int r,int c)
{

    check[r][c]=1;

    for(int i=0; i<8; i++)
    {
        int I=r+x[i];
        int J=c+y[i];
        if(((I>=0&&I<n)&&(J>=0&&J<n))&&check[I][J]==0)
        {
            check[I][J]=1;
            if(v[I][J]=='1')  dfs(I,J);
        }


    }
}

UVA 572 - Oil Deposits solution

#include <bits/stdc++.h>
#define sc scanf
#define pf printf
typedef long long ll;

using namespace std;
void dfs(int i,int j);

vector<string>v;
int row,col;
bool visit [101][101];

int x[]={-1,-1,-1,+0,+0,+1,+1,+1};
int y[]={-1,+0,+1,-1,+1,-1,+0,+1};

int main()
{

   // freopen("in.txt","r",stdin);
    while(sc("%d %d",&row,&col)==2)
    {
        v.clear();
        if(row==0&&col==0) break;
        for(int i=0; i<row; i++)
        {
            string s;
            cin>>s;
            v.push_back(s);
        }
        memset(visit,0,sizeof(visit));
        int cnt=0;

        for(int i=0; i<row; i++)
        {
            for(int j=0; j<col; j++)
            {
                if(visit[i][j]==0)
                {
                    visit[i][j]=1;
                    if(v[i][j]=='@')
                    {
                       cnt++;
                       dfs(i,j);

                    }

                }
            }
        }


         pf("%d\n",cnt);

    }


    return 0;

}

void dfs(int r,int c)
{
      visit[r][c]=1;

      for(int i=0;i<8;i++)
      {

          int I=r+x[i];
          int J=c+y[i];
          if((I>=0&&I<row)&&(J>=0&&J<col)&&visit[I][J]==0)
          {
              visit[I][J]=1;
            if(v[I][J]=='@')  dfs(I,J);
          }
      }

}