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 '.' cell we have to made 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 in A and b in B,now we start bfs from a and try to reack b. we will keep a vector FRM and DIR which will keep track of 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 node and save one node from each connected component as a head node.then if there are k connected components conncet ther 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 greedly if vertex is not visited color it white and run dfs . now color all its uncolored neighbour black 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 recursion stack we will add this vertex to an array CYCLE .now we will also keep track of which vertex is in recursion track by TILL this will help us to know till where we need to add nodes to cycle.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 GRID matxrix. Then you apply bfs from source and keep track of steps (initially 0) and go to only those nodes where septs are less than grid[x][y] means you only go to those cells where you can reach before any monster has arrived 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 AlgorithmYour text to link here...
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 tere is a positive cycle ending at k and if there if a cycle wheather there is a path like 1->k->n then ans is zero.if there is no such cycle you have to find biggest route from 1 to n. You can do this by using floyd warshal 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
what till you do is 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 minmum 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 negitve 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;
