I got bored with solving and wanted to do something which is related to cp and also very fun so i decided to write this tutorial.bare me for my bad English .
how to solve grid problems
here is my template to solve grid problems
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
string ds="RLDU";
int n,m;
bool possible(int x,int y){
//cout<<n<<" "<<m<<" "<<x<<" "<<y<<" possible"<<endl;
return (x<n&&x>=0&&y<m&&y>=0);
}
here we cand do just x+dx[i],y+dx[i] to move the four
directions and ds helps if we want to record path.
we can easily extend it to include four diagonals
1) counting rooms
For each unvisited '.' cell we have to make dfs(or bfs)
and keep on coloring the visited nodes.We keep track number
of dfs by count variable .our answer would be count.
void dfs(int x,int y){
if(!possible(x,y)||vis[x][y]!=-1||grid[x][y]==0)return ;
vis[x][y]=1;
int i;
fo(i,0,4){
int nx=x+dx[i],ny=y+dy[i];
dfs(nx,ny);
}
}
fo(i,0,n){
string s;
cin>>s;
fo(j,0,m){
if(s[j]=='.')grid[i][j]=1;
else grid[i][j]=0;
}
}
int ans=0;
fo(i,0,n){
fo(j,0,m){
if(grid[i][j]==1&&vis[i][j]==-1){
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
2) Labyrinth
We will store the coordinates of a and b ,now we start bfs
from a and try to reach b. We will keep a vector FRM and
DIR which will keep track of the cell from which we came here
and what is the direction of that move .At last if b is visited
we will go in reverse order by using FRM and try to recreate the path.
here a,b is coordinate of 'A' and c,d is coordinate of 'B'
queue<pii> q;
q.push({a,b});
vii from[n+1][m+1];
from[a][b].pb({0,0});
char ch[n+1][m+1];
while(!q.empty()){
pii p=q.front();
x=p.x;
y=p.y;
// cout<<from[x][y][0].x<<" "<<from[x][y][0].y<<" "<<x<<" "<<y<<" : ";
q.pop();
vis[x][y]=1;
if(grid[x][y]==3)break;
fo(i,0,4){
int nx=x+dx[i],ny=y+dy[i];
//cout<<x<<" "<<dx[i]<<","<<y<<" "<<dy[i]<<endl;
if(!possible(nx,ny))continue;
if(grid[nx][ny]==0||vis[nx][ny]!=-1)continue;
//cout<<"("<<nx<<","<<ny<<") ";
vis[nx][ny]=1;
q.push({nx,ny});
from[nx][ny].pb(p);
ch[nx][ny]=ds[i];
}
//cout<<endl;
}
if(vis[c][d]==-1){
cout<<"NO"<<endl;
return 0;
}
else{
cout<<"YES"<<endl;
pii p={c,d};
while(p.x!=a||p.y!=b){
s+=ch[p.x][p.y];
p=from[p.x][p.y][0];
}
reverse(all(s));
cout<<s.size()<<endl;
cout<<s<<endl;
}
3) Building Roads
The problem is basically connecting the disconnected components.
do dfs on all unvisited nodes and save one node from each
connected component as a head node.Then if there are k connected
components connect their head node via k-1 edges between heads.
vi v;
fo(i,1,n+1){
if(vis[i]==-1){
v.pb(i);
dfs(i);
}
}
cout<<v.size()-1<<endl;
fo(i,1,v.size()){
cout<<v[i]<<" "<<v[i]-1<<endl;
}
4) Message Route
This question is similar to Labyrinth ,start a bfs from 1 and
also keep vector FRM to know from where the current node is reached
and at last if n is visited go in reverse order using FRM to recreate path.
queue<int> q;
q.push(1);
while(!q.empty()){
int p=q.front();
q.pop();
vis[p]=1;
if(p==n)break;
for(int aa:graph[p]){
if(vis[aa]==-1){
from[aa]=p;
vis[aa]=1;
q.push(aa);
}
}
}
vi v;
if(vis[n]==-1){
cout<<"IMPOSSIBLE"<<endl;
}
else{
v.pb(n);
a=n;
while(a!=1){
a=from[a];
v.pb(a);
}
cout<<v.size()<<endl;
rfo(i,v.size()-1,0){
cout<<v[i]<<" ";
}
}
5) Building teams
The question is about coloring the bipartite graphs more about it.
we try to color all vertex greedily if vertex is not visited color
it white and run dfs . now color all its uncolored neighbors of white vertex
black and vice versa and run dfs on them.
at last check that each edge has ends with different colors.
void dfs(int p,int c){
if(vis[p]!=-1){
return ;
}
vis[p]=1;
color[p]=c;
for(int aa:graph[p]){
if(vis[aa]==-1)dfs(aa,1-c);
}
}
bool ok=true;
_init(vis);
fo(i,1,n){
if(vis[i]==-1){
dfs(i,0);
}
}
fo(i,0,m){
if(color[edges[i].x]==color[edges[i].y]){
ok=false;
break;
}
}
if(!ok){
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
fo(i,1,n+1){
cout<<color[i]+1<<" ";
}
6) Round Trip
Question is about finding cycle.We will run a dfs an keep vector VIS
to keep track of the nodes in the recusion stack.If we are at node p
we will run dfs no all of its childs if any of the child is in recursion
stack we will add this vertex to an array CYCLE . Now we will also keep
track of where to end cycle by TILL . If current is equal to TILL return from all dfs's else return TILL
int vis[N],from[N],color[N],till;
vi v;
int dfs(int p,int c){
//cout<<p<<" <<<"<<endl;
if(vis[p]!=-1){
till=p;
v.pb(p);
return 1;
}
vis[p]=1;
for(int aa:graph[p]){
if(aa==c)continue;
int x=dfs(aa,p);
//cout<<p<<" "<<aa<<" "<<x<<endl;
if(x==1){
v.pb(p);
if(till==p){
return 2;
}
else{
return 1;
}
}
else if(x==2)return 2;
}
vis[p]=2;
return 0;
}
7) Monsters
You have to do a multi source bfs from all the monsters . You keep track
of minimum step a monster can reach a cell in the GRID matrix
. Then you apply bfs from source and keep track of steps (initially 0)
and go to only those nodes where steps are less than grid[x][y] means
you only go to those cells where you can reach before any monster
has reached there. You can recreate path using FRM and DIR matrix as I have done in Labyrinth .
const int N=1001;
int grid[N][N];
string maze[N];
int vis[N][N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
string s;
vii mon;
int ax,ay;
fo(i,0,n){
cin>>s;
fo(j,0,m){
maze[i]=s;
if(s[j]=='A'){
ax=i;
ay=j;
}
if(s[j]=='M'){
mon.pb({i,j});
}
}
}
queue<pair<int,pii>> q;
_init(vis);
fo(i,0,mon.size()){
q.push({0,{mon[i].x,mon[i].y}});
vis[mon[i].x][mon[i].y]=1;
}
_init(grid);
while(q.size()>0){
pii p=q.front().y;
int lvl=q.front().x;
q.pop();
grid[p.x][p.y]=lvl;
fo(i,0,4){
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!possible(nx,ny))continue;
if(maze[nx][ny]=='#')continue;
if(vis[nx][ny]!=-1)continue;
q.push({lvl+1,{nx,ny}});
vis[nx][ny]=1;
}
}
/*
fo(i,0,n){
fo(j,0,m){
cout<<grid[i][j]<<" ";
}
cout<<endl;
}
cout.flush();
*/
_init(vis);
pair<int,int> from[n+1][m+1];
char dir[n+1][m+1];
s="RLDU";
q.push({0,{ax,ay}});
pii to={-1,-1};
bool mm=mon.size()>0;
while(q.size()>0){
pii p=q.front().y;
int lvl=q.front().x;
q.pop();
if(grid[p.x][p.y]!=-1&&lvl>=grid[p.x][p.y]){
//cout<<p.x<<" "<<p.y<<" "<<lvl<<" "<<grid[p.x][p.y]<<endl;
continue;
}
//cout<<p.x<<" "<<p.y<<":";
if(p.x==0||p.x==n-1||p.y==0||p.y==m-1){
to={p.x,p.y};
break;
}
fo(i,0,4){
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!possible(nx,ny))continue;
if(maze[nx][ny]=='#')continue;
if(vis[nx][ny]!=-1)continue;
if(grid[nx][ny]!=-1&&grid[nx][ny]<=lvl)continue;
from[nx][ny]=p;
q.push({lvl+1,{nx,ny}});
vis[nx][ny]=1;
dir[nx][ny]=s[i];
//cout<<"("<<nx<<","<<ny<<") ";
if(nx==0||nx==n-1||ny==0||ny==m-1){
//cout<<lvl<<" "<<
to={nx,ny};
break;
}
}
if(to.x!=-1)break;
//cout<<endl;
}
// cout<<to.x<<" "<<to.y<<" "<<ax<<" "<<ay<<endl;
if(to.x==-1){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
s="";
while(to.x!=ax||to.y!=ay){
s+=dir[to.x][to.y];
//cout<<to.x<<" "<<to.y
to=from[to.x][to.y];
}
reverse(all(s));
cout<<s.size()<<endl;
cout<<s<<endl;
return 0;
}
8) Shortest Routes I
The question ask you to implement simple dijsktra more about it
priority_queue<pii,vii,greater<pii>> q;
q.push({0,1});
_init(dis);
_init(vis);
dis[1]=0;
while(!q.empty()){
pii p=q.top();
q.pop();
int node=p.y,d=p.x;
if(vis[node]!=-1)continue;
vis[node]=1;
for(pii aa:graph[node]){
if(vis[aa.y]!=-1)continue;
if(dis[aa.y]==-1||dis[aa.y]>d+aa.x){
dis[aa.y]=d+aa.x;
q.push({d+aa.x,aa.y});
}
}
}
fo(i,1,n+1){
cout<<dis[i]<<" ";
}
9) Shortest Routes II
The question is about simple Floyd Warshall Algorithmmore about it
cin>>n>>m>>q;
fo(i,1,n+1){
fo(j,1,n+1){
mat[i][j]=inf;
}
mat[i][i]=0;
}
fo(i,0,m){
cin>>a>>b>>c;
mat[a][b]=min(mat[a][b],c);
mat[b][a]=min(mat[b][a],c);
}
int k;
fo(k,1,n+1){
fo(i,1,n+1){
fo(j,1,n+1){
mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
}
}
}
fo(i,0,q){
cin>>a>>b;
cout<<((mat[a][b]>=inf)?-1:mat[a][b])<<"\n";
}
10) High scores
Let say we are at node k we have to find weather there is a positive cycle ending
at k and if there if a cycle whether there is a path like 1->k->n then ans is zero.
You can do this by runnig dfs for each node and see if there is cycle ending at
that node with positive sum.if there is no such cycle you have to find biggest
route from 1 to n. You can do this by using bellman ford complexity o(n*m)
const int N=2501;
vii graph[N];
int vis[N],dis[N],from1[N],to1[N],fromn[N],ton[N],cycle[N];
int n,m,r,has1,hasn;
int findc(int p){
vis[p]=1;
if(p==1){
has1=1;
}
if(p==n){
hasn=1;
}
for(pii aa:graph[p]){
if(aa.x==r){
dis[p]=max(dis[p],aa.y);
continue;
}
if(vis[aa.x]==1)continue;
if(vis[aa.x]==2){
dis[p]=max(dis[p],dis[aa.x]+aa.y);
}
else{
int x=findc(aa.x);
if(x!=-inf){
dis[p]=max(dis[p],x+aa.y);
}
}
}
vis[p]=2;
return dis[p];
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
fo(i,1,n+1){
_init(vis);
_init(dis);
has1=0;
hasn=0;
r=i;
fo(j,0,n)dis[j+1]=-inf;
x=findc(i);
//cout<<x<<" "<<has1<<" "<<hasn<<endl;;
to1[i]=has1;
ton[i]=hasn;
cycle[i]=x>0;
if(i==1){
fo(j,0,n)from1[j+1]=vis[j+1];
}
if(i==n){
fo(j,0,n)fromn[j+1]=vis[j+1];
}
}
fo(i,1,n+1){
if(cycle[i]){
if(from1[i]>0&&ton[i]>0){
cout<<-1;
return 0;
}
else if(fromn[i]>0&&to1[i]>0){
cout<<-1;
return 0;
}
}
}
//cout<<endl;
fo(i,0,n)dis[i+1]=-inf;
dis[1]=0;
fo(i,1,n+1){
fo(j,1,n+1){
if(dis[j]==-inf)continue;
for(pii aa:graph[j]){
dis[aa.x]=max(dis[aa.x],dis[j]+aa.y);
}
}
}
cout<<dis[n]<<endl;
return 0;
}
11) Flight Discounts
Find minimum distance from 1 till starting of edge and minimum distance
from end of node till n and add weight/2. may be the concept involved here
is called meet in the middle not sure though.create two graphs original and reverse.
from original graph start dijkstra from 1 and store result in FRM1 and from
reverse graph start dijkstra from n and store result in TON .then iterate
through all edges and ans is minimum of (FRM1[edge[i].start + edge.weight/2 + TON[edge.end])
_init(vis);
_init(dis);
dis[0]=0;
priority_queue<pii,vii,greater<pii>> q;
q.push({0,0});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]!=-1)continue;
vis[p.y]=1;
for(pii aa:graph[p.y]){
if(vis[aa.x]!=-1)continue;
if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){
q.push({p.x+aa.y,aa.x});
dis[aa.x]=p.x+aa.y;
}
}
}
vi f1;
fo(i,0,n){
f1.pb(dis[i]);
}
_init(vis);
_init(dis);
dis[n-1]=0;
//pl();
q.push({0,n-1});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]!=-1)continue;
vis[p.y]=1;
//cout<<p.x<<" "<<p.y<<endl;
for(pii aa:rev[p.y]){
if(vis[aa.x]!=-1)continue;
if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){
q.push({p.x+aa.y,aa.x});
dis[aa.x]=p.x+aa.y;
}
}
}
// pl();
vi fn;
fo(i,0,n){
fn.pb(dis[i]);
}
//cout<<f1<<endl;
//cout<<fn<<endl;
int ans=f1[n-1];
for(piii bb:edges){
pii aa=bb.y;
if(f1[aa.x]!=-1&&fn[aa.y]!=-1){
ans=min(ans,f1[aa.x]+fn[aa.y]+bb.x/2);
}
}
cout<<ans<<endl;
12)Finding Cycles
This problem can be solved using bellman ford algorithm .
the key idea is relax each edge n(number of node) times if there is no negative cycle
then because you should have got the final answer in n-1 iterations itself
which means if there is a negative cycle only then there will be some changes in nth iteration
so this way you can detect the cycle and you can regenerate if using FRM array
in depht explanation
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
fo(i,1,n+1)dis[i]=inf;
dis[1]=0;
vi baap(n+1,-1);
fo(i,0,n+1){
till=-1;
fo(j,1,n+1){
for(pii p:graph[j]){
if(dis[p.x]>dis[j]+p.y){
dis[p.x]=dis[j]+p.y;
baap[p.x]=j;
till=p.x;
}
}
}
}
if(till==-1){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
fo(i,0,n){
till=baap[till];
}
vi cyc;
for(int aa=till;;aa=baap[aa]){
cyc.pb(aa);
if(cyc.size()>1&&aa==till){
break;
}
}
reverse(all(cyc));
cout<<cyc<<endl;
13) Flight Routes
Important observaion here is k is very small (k<10) and
if you want to find k routes each vertex is visited atmax k times in k routes.
so it is someting like dijkstra you keep CNT array were you keep count of each node
and take a min heap(set or priority queue in cpp) and insert 1st node with cost 0
in it. Now let say p is smallest node in heap. increase count of p in CNT array
if it is more than k then continue to next iteration.if p is last node add cost
to ANS array.now iterate through all edges of p and add child with cost p.cost + edge weight
in the heap.
now just print ans array complexity o(nmk).more about it
const int N=1e5+5;
vii graph[N];
int dis[N],vis[N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m,k;
cin>>n>>m>>k;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;a--;b--;
graph[a].pb({b,c});
}
priority_queue<pii,vii,greater<pii>> q;
_init(dis);
_init(vis);
dis[0]=0;
q.push({0,0});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]==1)continue;
vis[p.y]=1;
for(auto aa:graph[p.y]){
if(vis[aa.x]==-1){
if(dis[aa.x]==-1||dis[aa.x]>aa.y+p.x){
dis[aa.x]=aa.y+p.x;
q.push({dis[aa.x],aa.x});
}
}
}
}
/* fo(i,0,n){
cout<<dis[i]<<" ";
}*/
int count[n+1];
_init0(count);
vi v;
q.push({0,0});
int cnt=k;
while(!q.empty()&&count[n-1]<k){
pii p=q.top();
q.pop();
count[p.y]++;
if(p.y==n-1){
v.pb(p.x);
}
if(count[p.y]<=k){
for(auto aa:graph[p.y]){
q.push({p.x+aa.y,aa.x});
}
}
}
sort(all(v));
cout<<v<<endl;
return 0;
}
Hope this is helpfull to you . I will try to add more as I solve furthure.
