[search] flood fill and shortest path model

---

Flood Fill 

Flood filling (Flood fill) Algorithm ： Start from a starting node and put nearby Connect with it The nodes of are extracted or filled into different colors , Until all nodes in the enclosed area have been processed , yes Several connected points are extracted from a region to distinguish it from other adjacent regions ( Or dyed into different colors ) The classic algorithm .

Can be in Linear time complexity Inside , Find a point where Connected block  

If the DFS, There may be “ Burst the stack ” Danger , So we usually use BFS To implement this algorithm

---

AcWing 1097. Pond count  

sample input ：

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

sample output ：

3

---

 

---

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;
    
    while(hh <= tt)
    {
        auto t = q[hh ++ ];
        
        for(int i = t.x - 1; i <= t.x + 1; i ++ )
            for(int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if(i == t.x && j == t.y) continue;
                if(i < 0 || i >= n || j < 0 || j >= m) continue;
                if(g[i][j] == '.' || st[i][j]) continue;
                
                q[++ tt ] = {i, j};
                st[i][j] = true;
            }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )
    {
        scanf("%s", g[i]);
    }
    
    int cnt = 0;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            if(g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++ ;
            }
    
    cout << cnt << endl;
    
    return 0;
}

---

AcWing 1098. The castle problem  

 

sample input ：

4 7 
11 6 11 6 3 10 6 
7 9 6 13 5 15 5 
1 10 12 7 13 7 5 
13 11 10 8 10 12 13 

sample output ：

5
9

---

The difficulty of this problem lies in Initial mapping On

According to the conditions given by the topic , according to Binary format To build a map  

---

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

const int N = 55, M = N * N;

int n, m;
int g[N][N];
PII q[M];
bool st[N][N];

int bfs(int sx, int sy)
{
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
    
    int hh = 0, tt = 0;
    int area = 0;
    
    q[0] = {sx, sy};
    st[sx][sy] = true;
    
    while(hh <= tt)
    {
        auto t = q[hh ++ ];
        
        for(int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(st[a][b]) continue;
            if(g[t.x][t.y] >> i & 1) continue;
            
            q[ ++ tt] = {a, b};
            st[a][b] = true;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            cin >> g[i][j];
            
    int cnt = 0, area = 0;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
        if(!st[i][j])
        {
            area = max(area, bfs(i, j));
            cnt ++ ;
        }
    cout << cnt << endl;
    cout << area << endl;
    
    return 0;
}

---

AcWing 1106. Mountains and valleys   

 

sample input 1：

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

sample output 1：

2 1

sample input 2：

5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

sample output 2：

3 3

---

 

---

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int h[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy, bool& has_higher, bool& has_lower)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;
    
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        
        for(int i = t.x - 1; i <= t.x + 1; i ++ )
            for(int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if(i < 0 || i >= n || j < 0 || j >= n) continue;
                if(h[i][j] != h[t.x][t.y]) // The boundary of the mountains 
                {
                    if(h[i][j] > h[t.x][t.y]) has_higher = true;
                    else has_lower = true;
                }
                else if(!st[i][j])
                {
                    q[++ tt] = {i, j};
                    st[i][j] = true;
                }
                
            }
    }
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            scanf("%d", &h[i][j]);
    int peak = 0, valley = 0;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++)
        if(!st[i][j])
        {
            bool has_higher = false, has_lower = false;
            bfs(i, j, has_higher, has_lower);
            if(!has_higher) peak ++ ;
            if(!has_lower) valley ++ ;
        }
    printf("%d %d\n",peak, valley);
    
    return 0;
}

---

Shortest path model  

utilize The shortest of wide search , It can be used Width first search , stay Linear time complexity Inside , find shortest path

---

AcWing 1076. Maze problem  

sample input ：

5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

sample output ：

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

---

(BFS) 
Depth first search timeout

from (n - 1, n - 1) - > (0, 0) Do breadth first search , Using an array to store the current node is From which node

---

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int g[N][N];
PII q[M];
PII pre[N][N]; //  Record path 

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    
    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0};
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        
        for(int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(g[a][b]) continue;
            if(pre[a][b].x != -1) continue;
            
            q[++ tt] = {a, b};
            pre[a][b] = t;
        }
    }
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            scanf("%d", &g[i][j]);
            
    bfs(n - 1, n - 1);
    
    PII end(0, 0);
    
    while(1)
    {
        printf("%d %d\n", end.x, end.y);
        if(end.x == n - 1 && end.y == n - 1) break;
        end = pre[end.x][end.y];
    }
    
    return 0;
}