Red and black "BFS" - BFS, Red and black

There is a rectangular house with square tiles in red and black on the floor. You stand on one of the black tiles and can only move to the adjacent black tile. Please write a program to calculate how many black tiles you can reach in total. Input includes multiple data sets. The first row of each data set is two integers W and H, which represent the number of tiles in the x-direction and y-direction, respectively. W and H are not more than 20. In the next H lines, each line includes W characters. Each character represents the color of a tile, and the rules are as follows:
1)’.’: black tiles;
2)’#’: white tiles ;
3)’@’: A black tile, and you are standing on this tile. This character appears only once in each data set.
When two zeros are read in a row, it means that the input is over.
Output outputs a row for each data set, showing the number of tiles you can reach from the initial position (including the tiles at the initial position when counting). Sample Input

6 9

....#.

.....#

......

......

......

......

......

#@...#

.#..#.

0 0

Sample Output

45

BFS can run naked, remember the last +1 (starting position), and then enter the pits. The input is a few columns and rows, not a few rows and several columns< /span>

#include  #include   #include  #include <string> #include  #include   #include  #include  #include <set> #include   #include  #include 

using namespace std; #define ull unsigned long long

#define lli long long

#define pq priority_queue

#define pql priority_queue

#define pqn priority_queue

#define v vector

#define vl vector

#define read(x) scanf("%d",&x)

#define lread(x) scanf("%lld",&x);

#define pt(x) printf("%d
",(x))

#define YES printf("YES
");

#define NO printf("NO
");

#define gcd __gcd

#define out(x) cout<#define over cout<#define rep(j,k) for (int i = (int)(j); i <= (int)(k); i++)

#define input(k) for (int i = 1; i <= (int)(k); i++) {scanf("% d",&a[i]);}

#define mem(s,t) memset(s,t,sizeof(s))

#define ok return 0;

#define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define mod(x) ((x)%9973)

#define test cout<<" ++++++ "<//Binary Tree

#define lson rt<<1, l, m

#define rson rt<<1|1, m+1, r

//Line segment tree

#define ls now<<1

#define rs now<<1|1

const int MAXN = 2e5+5; //int dir[6][3] = {0,0,1,0,0,-1,1,0,0,-1,0,0,0,1,0,0,- 1,0};

int dir[4][2] = {1,0,-< span style="color: #800080;">1,0,0 span>,1,0,-1}; //Unit move//int dir[8][2] = {2,1,2,-1,-2,1,- 2,-1,1,2,1,-2,-1,2,-1,-2};

int t,n,m,x,y,col,ex,ey,ans ,ly,flag; struct node {int id; int x,y; }; node no,nx; char str[20+5][20+5]; int< span style="color: #000000;"> main() {TLE; while(cin>>n>>m&&n&&m) {for(int i=0; i) for(int j=0; j) {cin>>str[i][j]; < /span>if(str[i][j]=='@') no.x=i,no.y=j,no;} queueq; q.push (no); ans = 0; str[no.x][no.y ] = '#'; while(!q.empty()) {nx = q.front(); q.pop(); for(int i=0; i<4 ; i++) {no.x = nx.x+dir[i][0 ]; no.y = nx.y+dir[i][1 span>]; if(no.x<0 || no.y<0 ||no.x>=m ||no.y>=n) < span style="color: #0000ff;">continue; if (str[no.x][no.y] =='.') {ans++; str [no.x][no.y] = '#< span style="color: #800000;">'; q.push(no);}}} cout<1<<endl;} ok; }

#include  #include  #include  #include <string> #include  #include  #include  #include  #include <set> #include  #include  #include 

using namespace std; #define ull unsigned long long

#define lli long long

#define pq priority_queue

#define pql priority_queue

#define pqn priority_queue

#define v vector

#define vl vector

#define read(x) scanf("%d",&x)

#define lread(x) scanf("%lld",&x);

#define pt(x) printf("%d
",(x))

#define YES printf("YES
");

#define NO printf("NO
");

#define gcd __gcd

#define out(x) cout<#define over cout<#define rep(j,k) for (int i = (int)(j); i <= (int)(k); i++)

#define input(k) for (int i = 1; i <= (int)(k); i++) {scanf("% d",&a[i]);}

#define mem(s,t) memset(s,t,sizeof(s))

#define ok return 0;

#define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define mod(x) ((x)%9973)

#define test cout<<" ++++++ "<//Binary Tree

#define lson rt<<1, l, m

#define rson rt<<1|1, m+1, r

//Line segment tree

#define ls now<<1

#define rs now<<1|1

const int MAXN = 2e5+5; //int dir[6][3] = {0,0,1,0,0,-1,1,0,0,-1,0,0,0,1,0,0,- 1,0};

int dir[4][2] = {1,0,-< span style="color: #800080;">1,0,0 span>,1,0,-1}; //Unit move//int dir[8][2] = {2,1,2,-1,-2,1,- 2,-1,1,2,1,-2,-1,2,-1,-2};

int t,n,m,x,y,col,ex,ey,ans ,ly,flag; struct node {int id; int x,y; }; node no,nx; char str[20+5][20+5]; int< span style="color: #000000;"> main() {TLE; while(cin>>n>>m&&n&&m) {for(int i=0; i) for(int j=0; j) {cin>>str[i][j]; < /span>if(str[i][j]=='@') no.x=i,no.y=j,no;} queueq; q.push (no); ans = 0; str[no.x][no.y ] = '#'; while(!q.empty()) {nx = q.front(); q.pop(); for(int i=0; i<4 ; i++) {no.x = nx.x+dir[i][0 ]; no.y = nx.y+dir[i][1 span>]; if(no.x<0 || no.y<0 ||no.x>=m ||no.y>=n) < span style="color: #0000ff;">continue; if (str[no.x][no.y] =='.') {ans++; str [no.x][no.y] = '#< span style="color: #800000;">'; q.push(no);}}} cout<1<<endl;} ok; }

Red and black “BFS”

Leave a Comment Cancel reply