Mohammad Erfan Hossain's Blog

UVA 10986 Solution - Sending email uva id: shoaib05 Accepted Time: 0.379 I used priority queue and Dijkstra Algorithm. Code: #include<iostream> #include<vector> #include<algorithm> #include<map> #include<queue> #include<cstring> using namespace std; typedef pair<int,int> pii; typedef vector<pii> vecpii; map<int,vecpii> mymap; map<int,int> result; bool visit[20010]; class Compare { public: bool operator()(pii p1,pii p2) { return p1.second>p2.second; } }; int DjKastra(int x,int y) { priority_queue<pii,vector<pii>,Compare> q; pii p,temp; int i; memset(visit,false,sizeof(visit)); q.push(pii(x,0)); while(!q.empty()) { p=q.top(); if(p.first==y) return p.second; q.pop(); if(visit[p.first]) continue; visit[p.first]=true; for(i=0;i<mymap[p.first].size();i++) { temp=mymap[p.first][i]; if(!visit[temp.first]) { q.push(pi...

UVA 429 Solution - Word Transformation uva id: shoaib05 Accepted Time: 0.036 I used Edit_Distance and Floyd warshall algorithm. Every word acts as a node. Two nodes are  adjacent if their edit distance is One . map, may ,mad are adjacent of each other. But pad and map are not adjacent because their edit distance is 2 . But mad and pad are adjacent because their edit distance is 1 . Here has no link between may and pad, no link between map and pad. Code: #include<iostream> #include<string> #include<algorithm> #include<map> #include<stdio.h> #define COLUMN 210 #define INFINITE 100000 using namespace std; int editDistance(string str1,string str2) { int table[11][11],length1,length2,i,j; length1=str1.size(); length2=str2.size(); for(i=0;i<=length1;i++) table[0][i]=i; for(i=1;i<=length2;i++) table[i][0]=i; for(i=1;i<=length2;i++) { for(j=1;j<=length1;j++) { ...

C++ Code for Kruskal's Algorithm with explanation  Example: Node numbers are 1 2 3 4 5 Weight is 3 between 1 and 3.  Weight is 4 between 1 and 2. Weight is 9 between 2 and 3. Weight is 1 between 2 and 4. Weight is 7 between 5 and 3. Weight is 2 between 4 and 5. At first sort the edge list according to weight. Weight is 1 between 2 and 4. Weight is 2 between 4 and 5. Weight is 3 between 1 and 3.  Weight is 4 between 1 and 2. Weight is 7 between 5 and 3. Weight is 9 between 2 and 3. Take array for node's parent. And initialize parent value equal to node value. parent[1]=1 parent[2]=2 parent[3]=3 parent[4]=4 parent[5]=5 Select the most small weighted edge. Here it is : Weight is 1 between 2 and 4. check the parents of two nodes are equal or not. If parents are not equal, Then store it in answer container. And set 2nd's node parent is 1st node's parent. parent of node 2 is 1. parent of node 4 is 2. p...

UVA 11504 Solution- Dominos uva id: shoaib05 Accepted Time: 0.312   #include<iostream> #include<set> #include<vector> #include<algorithm> #include<string.h> using namespace std; typedef pair<int,int> Pair_Int_Int; vector<int> edge[100010]; vector<Pair_Int_Int> answer; set<int> myset; bool visit[100010]; int in_time; Pair_Int_Int p; bool mysort(Pair_Int_Int p1, Pair_Int_Int p2) {     return p1.second>p2.second; } void topological_sort(int x) {     visit[x]=true;     myset.erase(x);     int i,y;     for(i=0;i<edge[x].size();i++)     {         y=edge[x][i];         if(visit[y]==false)         {             in_time++;             topological_sort(y);...

UVA 11838 Solution- Come and Go uva id: shoaib05  Accepted Time: 0.192 #include<iostream> #include<string.h> using namespace std; bool table[2010][2010]; int value[2010]; int main() {     int n,m,i,j,k,x,y,d,res;     while(cin>>n>>m)     {         if(m==0 && n==0)             break;         memset(value,0,sizeof(value));         memset(table,false,sizeof(table));         for(i=1;i<=m;i++)         {             cin>>x>>y>>d;             table[x][y]=true;             value[x]++;             if(d==2)  ...

UVA 776 Solution- Monkeys in a Regular Forest  It is simply floodfill problem. Here change is taking input and print correctly. Two consecutive input is separated by % sign. Finally EOF is the end of last input. Main challenge is displaying output. Before displaying, should calculate the max width of a column. Then display the each element with max width. I used width array to calculate the max width of every column.    uva id: shoaib05 Accepted Time : 0.036 #include<cstdio> #include<cstring> #include<stack> #include<iostream> #include<iomanip> using namespace std; typedef pair<int,int> pr; pr p; int len,row,col; char graph[1000][1000],input[2000]; int result[1000][1000],num; int dx[] = {-1,-1,-1,0,0,1,1,1}; int dy[] = {-1,0,1,-1,1,-1,0,1}; bool flag=true,vis[1000][1000]; void floodfill(int xx,int yy) { result[xx][yy]=num; stack<pr> st; p=pair<int,int>(xx,yy); st.push(p); char...

UVA 722 Solution- Lakes uva id: shoaib05 Accepted Time: 0.000 #include<cstdio> #include<cstring> #include<stack> using namespace std; typedef pair<int,int> pr; int main()  { int N, a, b, n, m,ans,i,x,y; char inp[110]; char graph[100][100]; bool vis[100][100]; int dx[4] = { 0, 0, -1, 1 }; int dy[4] = { 1, -1, 0, 0 }; stack<pr> st; pr p;     scanf("%d", &N);     while(N--) {         scanf("%d %d", &a, &b);         a--; b--;         memset(vis, false, sizeof vis);         n = 0; getchar();         while(gets(inp) && strlen(inp) > 0) {             strcpy(graph[n], inp);             n++;         }         m = strlen(graph[0]); ans=0; if(graph[a][b]=='0') { ans...

UVA 10116 Solution- Robot Motion uva id: shoaib05 Accepted Time: 0.000 #include<stdio.h> char table[105][105]; int visit[105][105]; int main() { int row,col,i,j,x,y,total_step,flag; char ch; while(scanf("%d %d %d",&row,&col,&y)) { if(row==0 && col==0 && y==0) break; y--; x=0; total_step=0; row--; col--; for(i=0;i<=row;i++) for(j=0;j<=col;j++) visit[i][j]=0; for(i=0;i<=row;i++) scanf("%s",&table[i]); flag=0; while(1) { if(visit[x][y]!=0) { flag=1; break; } visit[x][y]=++total_step; ch=table[x][y]; switch(ch) { case 'E': y++; break; case 'W': y--; break; case 'N': x--; ...