[AcWing算法提高课]之搜索（Flood

 思路解析：

最大房间的面积-->>也就是flood fill 的连通块的最大个数即可

画图理解：

颜色围着的表示房间的面积

难点在于刚开始的输入：

（1）（题目概述）：  1表示西墙  2表示北墙  4表示东墙  8表示南墙

首先 4 7 表示行与列不用过多介绍

然后11=8+2+1 表示这个点有  西墙 北墙 南墙

6=4+2  表示这个点 有 东墙 北墙

首先不要被这种有点华丽的东西吓到，先想想这个数字的规律：1 2 4 8

很明显是2倍的关系--->>但是好像不沾边--->>没关系我们换到二进制去想

1:0001

2:0010

4:0100

8:1000

答案出来了：只要这个地方为1，那么就证明有墙，那么在想想西北东南，这不就是我平常习惯的方向数组的方向吗，那么就证明只要扩展的该点>>i&1，如果为真那么就证明该点有墙无法通过，好了分析到这里，其实相较于模板而言，只是改变了模板判断墙壁的方式罢了

#include 
#include 
#include 
#include 
#define x first
#define y second

using namespace std;

typedef pair PII;

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

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

int bfs(int sx, int sy)
{
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

    
    int area = 0;

    q.push({sx,sy});
    st[sx][sy] = true;

    while (q.size())
    {
        auto t=q.front();
        q.pop();
        area ++ ;

        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;//&1为真-->>证明这个方位有墙-->>无法通过

            q.push({a,b});
            st[a][b] = true;
        }
    }

    return area;
}

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;
}

 核心思路：注释已经写得很清楚了

        核心就是如果，以该点为源点，周围没有比它高的，也就是has_higer=false

        那么就意味着源点就是山峰

        同理

        那么就意味着源点就是山谷

        else if 如果与源点相同且未被遍历过，那么就加入队列中

#include
#include
#include
#include
using namespace std;

#define x first
#define y second
typedef pair PII;
const int N=1010,M=N*N;
int n;
int h[N][N];
queue q;
bool st[N][N];

void bfs(int sx,int sy,bool &has_higher,bool &has_lower)
{
    q.push({sx,sy});
    st[sx][sy]=true;

    while(q.size())
    {
        PII t=q.front();
        q.pop();

        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>=n) continue;//跳过越界
                //注意以下的if and else if只有执行一个
                if(h[i][j]!=h[t.x][t.y])//如果扩展的该点！=原先的点的高度
                {
                    if(h[i][j]>h[t.x][t.y]) has_higher=true;//比原来的点高-->>证明存在山峰
                    else has_lower=true;//比原来的点低--->>证明存在谷底
                }
                else if(!st[i][j])//如果是第一次经过该点且该点与t这个点相等--->>入队
                {
                    q.push({i,j});
                    st[i][j]=true;
                }
            }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i>也可以写在bfs中
            {
                bool has_higher=false;
                bool 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;
}

 思路解析：

从终点开始搜索

用memory存路径

详细见注释

#include 
#include 
#include 
#define x first
#define y second

using namespace std;
typedef pair PII;
const int N = 1010;

int g[N][N];
PII memory[N][N];

int st[N][N];
int n;

void bfs()
{
    queue q;
    q.push({n - 1,  n - 1});//逆向走
    st[n - 1][n - 1] = true;
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
    while(q.size())//从终点到起点
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++)
        {
            int x = dx[i] + t.x, y = dy[i] + t.y;
            if(x < 0 || x >= n || y < 0 || y >= n)continue;
            if(st[x][y])continue;
            if(g[x][y] == 1)continue;
            q.push({x, y});
            st[x][y] = true;
            memory[x][y] = t;//记录(x,y)是由t更新的
            //memroy[x][y]一定是由大-->>小的
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> g[i][j];
    bfs();
    PII end = {0, 0};//先放入源点
    cout << 0 << ' ' << 0 << endl;

    while(end.x != n - 1 || end.y != n - 1)//从起点开始遍历，当end!=终点就继续
    {   
        printf("%d %d\n", memory[end.x][end.y].x, memory[end.x][end.y].y);
        //(0,0)的下一个位置是:[end.x],[end.y]对它.x .y就是由它更新的
        int x = end.x, y = end.y;//接受
        end.x = memory[x][y].x, end.y = memory[x][y].y;//更新的点又变为了被更新的点
    }

    return 0;
}

 纯纯板子___不过多介绍

#include 
#include 
using namespace std;
typedef pair PII;
int C, R;
char g[155][155];
int d[155][155];
int x, y, H_x, H_y;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
void bfs(int x, int y) {
    queue q;
    q.push({x, y}); d[x][y] = 0;
    while (q.size()) {
        auto t = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            int a = dx[i] + t.first, b = dy[i] + t.second;
            if (d[a][b] || g[a][b] == '*') continue;
            if (a < 0 || a >= C || b < 0 || b >= R) continue;
            d[a][b] = 1 + d[t.first][t.second];
            q.push({a, b});
        }
    }
}
int main() {
    cin >> R >> C;
    for (int i = 0; i < C; i++)
        scanf("%s", g[i]);
    for (int i = 0; i < C; i++)
        for (int j = 0; j < R; j++) {
            if (g[i][j] == 'K') 
                x = i, y = j;
            if (g[i][j] == 'H')
                H_x = i, H_y = j;
        }
    bfs(x, y);
    cout << d[H_x][H_y] << endl;
    return 0;
}

 核心思路：

BFS找最短路：

dist[N]数组作为记录步数

queue存idx，即数字

#include
#include
#include
#include
using namespace std;

const int N=2e5+10;
int n,k;
int dist[N];
queue q;

int bfs()
{
    memset(dist,-1,sizeof dist);
    dist[n]=0;
    q.push(n);

    while(q.size())
    {
        int t=q.front();
        q.pop();

        if(t==k) return dist[k];

        if(t+1=0 && dist[t-1]==-1)
        {
            dist[t-1]=dist[t]+1;
            q.push(t-1);
        }
        if(t*2>n>>k;
    cout<

#include 
#include 
#include 

using namespace std;

const int N = 1e3 + 10;

int n, m;
char g[N][N];
int dist[N][N];

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

void bfs()
{
    queue> q;
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '1') {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }

    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                continue;
            }
            if (dist[x][y] == -1) {
                dist[x][y] = dist[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }

    bfs();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j > 0) {
                cout << " ";
            }
            cout << dist[i][j];
        }
        cout << endl;
    }

    return 0;
}

#include
#include
#include
#include
using namespace std;

unordered_map >from;
// *** 作数
string mA(string now)
{
    reverse(now.begin(),now.end());
    return now;
}

string mB(string now)
{
    for(int i=3;i>0;i--)
    {
        swap(now[i],now[i-1]);
        swap(now[7-i],now[8-i]);
    }
    return now;
}

string mC(string now)
{
    swap(now[1],now[2]);
    swap(now[1],now[5]);
    swap(now[1],now[6]);
    return now;
}

void bfs(string begin,string end)
{
    queue q;
    q.push(begin);
    from[begin]={' '," "};//string ->(char,string)
    
    while(q.size())
    {
        string now=q.front();
        q.pop();

        string m[3]={mA(now),mB(now),mC(now)};//记录已经产生的结果-->>方位数组
        
        for(int i=0;i<3;i++)
        {
            if(!from.count(m[i]))//此操作得到的字符串没被遍历过
            {
                from[m[i]]={'A'+i,now};//存储来源-->>(从哪一步来， *** 作的字符串是什么)
                if(m[i]==end)//如果 *** 作后字符串与结果一样-->>找到-->退出
                {
                    return;
                }
                q.push(m[i]);//入队
            }
        }
    }
}

int main()
{
    string begin="12345678";
    string end;
    for(int i=0;i<8;i++)
    {
        int x;
        scanf("%d",&x);
        end+=char(x+'0');
    }

    if(begin!=end) bfs(begin,end);

    string res;
    while(end!=begin)//记录路径
    {
        res+=from[end].first;
        end=from[end].second;
    }
    reverse(res.begin(),res.end());
    cout<