CF1105D-KILANI AND THE GAME- (Multi-directional BFS)

By Game

http://codeforces.com/problemset/problem/1105/D

The meaning of the title: There is a matrix area. At the beginning, there are multiple forces such as 1, 2, 3, 4….9, starting from the force 1 and expanding outwards in turn, the map is’.’ which can be occupied, and’#’ cannot be occupied. After being occupied, you can’t be occupied by others again, you can only expand up, down, left, and right. Each force has an expansion speed. Find how many grids each force occupies in the entire area.

Problem solving:

1. Obviously bfs, but the speed varies greatly, and multi-directional bfs

2. The input data may have more than one starting point of the same force (pit)

3. Starting from force 1 to expand in turn, not the queue to the end at once

#include

#include

#include

#include

#include

#include<string>

#include

#include

#include

#include<set>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;





int n,m,p;

int last[10];///How many points were pressed in the last time

struct node

{

 int x;

 int y;

};

int s[10];///Speed

char a[1005][1005];

int vis[1005][1005];

int ans[10];

int can[10];///Is there no way out?

queueque[10];

int d[4][2]={ {-1,0< /span>}, {1,0}, {0,-1}, {0 ,1} };///Up, down, left, and right



void bfs()

{

 for(int i=1;i<=p;i++)///Empty

 {

 while(!que[i].empty())

 que[i].pop();

}

 for(int i=0;i)

 {

 for(int j=0;j)

 {

 if( a[i][j]!='.' && a[i][j]!='#')

 {

 que[ a[i][j]-'0 span>' ].push( {i,j} );///< span style="color: #008000;">Press the starting point, there may be more than one

 vis[i][j]=a[i][j]-'0 ';

 last[ a[i][j]-'0 span>' ]++;



}

}

}

 bool flag=true;

 while(flag)///If someone can extend, continue

 {

 flag=false;

 for(int idx=1;idx<=p;idx++)///Walk once per queue

 {

 for(int ss=1;ss<=s[idx] && can[idx]==0 ;ss++)///Expansion speed, how many steps can be taken, s[i] may be very timeout, truncated with the can array< /span>

 {

 int num=last[idx];///The number of nodes that are allowed to pop up to expand this time, that is, the number of nodes that were pushed in the last time

 last[idx]=0;///The nodes added in the new round of expansion should be cleared

 for(int t=1;t<=num;t++)

 {

 node now=que[idx].front();

 que[idx].pop();

 ans[idx]++;///take the head of the team, Area +1 when it pops up

 for(int i=0;i<4;i++)

 {

 int xx=now.x+d[i][0< /span>];

 int yy=now.y+d[i][1< /span>];

 if( xx>=0 && xx=0 && yy0 && a[xx][yy]=='.')

 {

 que[idx].push( {xx,yy} );

 vis[xx][yy]=idx;///Press Enqueue, mark visited

 last[idx]++;///The number of press-in points this time 

}

}



}

 if(que[idx].empty())

 can[idx]=idx;///There is no way out, the virtues expand Up

}

}

 for(int i=1;i<=p;i++)

 {

 if(!que[i].empty())

 flag=true;

}

}

 for(int i=1;i<=p;i++)

 printf("%d ",ans[i]);

 printf("
");

}



int main()///CF1105D

{

 while(scanf("%d %d %d",&n,&m,&p)!=EOF)

 {

 memset(a,0,sizeof(a));

 memset(s,0,sizeof(s));

 memset(ans,0,sizeof(ans));

 memset(vis,0,sizeof(vis));

 memset(last,0,sizeof(last));

 memset(can,0,sizeof(can));

 for(int i=1;i<=p;i++)///Speed

 scanf("%d",&s[i]);

 getchar();

 for(int i=0;i/// Map

 scanf("%s",a[i]);



 bfs();

}

 return 0;

}

#include

#include

#include

#include

#include

#include<string>

#include

#include

#include

#include<set>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;





int n,m,p;

int last[10];///How many points were pressed in the last time

struct node

{

 int x;

 int y;

};

int s[10];///Speed

char a[1005][1005];

int vis[1005][1005];

int ans[10];

int can[10];///Is there no way out?

queueque[10];

int d[4][2]={ {-1,0< /span>}, {1,0}, {0,-1}, {0 ,1} };///Up, down, left, and right



void bfs()

{

 for(int i=1;i<=p;i++)///Empty

 {

 while(!que[i].empty())

 que[i].pop();

}

 for(int i=0;i)

 {

 for(int j=0;j)

 {

 if( a[i][j]!='.' && a[i][j]!='#')

 {

 que[ a[i][j]-'0 span>' ].push( {i,j} );///< span style="color: #008000;">Press the starting point, there may be more than one

 vis[i][j]=a[i][j]-'0 ';

 last[ a[i][j]-'0 span>' ]++;



}

}

}

 bool flag=true;

 while(flag)///If someone can extend, continue

 {

 flag=false;

 for(int idx=1;idx<=p;idx++)///Walk once per queue

 {

 for(int ss=1;ss<=s[idx] && can[idx]==0 ;ss++)///Expansion speed, how many steps can be taken, s[i] may be very timeout, truncated with the can array< /span>

 {

 int num=last[idx];///The number of nodes that are allowed to pop up to expand this time, that is, the number of nodes that were pushed in the last time

 last[idx]=0;///The nodes added in the new round of expansion should be cleared

 for(int t=1;t<=num;t++)

 {

 node now=que[idx].front();

 que[idx].pop();

 ans[idx]++;///take the head of the team, Area +1 when it pops up

 for(int i=0;i<4;i++)

 {

 int xx=now.x+d[i][0< /span>];

 int yy=now.y+d[i][1< /span>];

 if( xx>=0 && xx=0 && yy0 && a[xx][yy]=='.')

 {

 que[idx].push( {xx,yy} );

 vis[xx][yy]=idx;///Press Enqueue, mark visited

 last[idx]++;///The number of press-in points this time 

}

}



}

 if(que[idx].empty())

 can[idx]=idx;///There is no way out, the virtues expand Up

}

}

 for(int i=1;i<=p;i++)

 {

 if(!que[i].empty())

 flag=true;

}

}

 for(int i=1;i<=p;i++)

 printf("%d ",ans[i]);

 printf("
");

}



int main()///CF1105D

{

 while(scanf("%d %d %d",&n,&m,&p)!=EOF)

 {

 memset(a,0,sizeof(a));

 memset(s,0,sizeof(s));

 memset(ans,0,sizeof(ans));

 memset(vis,0,sizeof(vis));

 memset(last,0,sizeof(last));

 memset(can,0,sizeof(can));

 for(int i=1;i<=p;i++)///Speed

 scanf("%d",&s[i]);

 getchar();

 for(int i=0;i/// Map

 scanf("%s",a[i]);



 bfs();

}

 return 0;

}

, , , , ,

Leave a Comment

Your email address will not be published.