全球变暖

# 求细胞数量

## 题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

## 输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 `0` 到 `9` 的字符串，代表这个 $n \times m$ 的矩阵。

## 输出格式

一行一个整数代表细胞个数。

## 样例 #1

### 样例输入 #1

```
4 10
0234500067
1034560500
2045600671
0000000089
```

### 样例输出 #1

```
4
```

## 提示

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。



直接dfs
```cpp
#include <iostream>
using namespace std;

int n, m;
int matrix[105][105];
bool visited[105][105];

// 方向数组，用于DFS遍历上下左右四个方向
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// DFS函数
void dfs(int x, int y) {
    visited[x][y] = true;
    
    // 遍历四个方向
    for (int i = 0; i < 4; ++i) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        
        // 检查是否越界，是否是细胞数字，是否未访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] != 0 && !visited[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    
    // 读取矩阵
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = row[j] - '0';
        }
    }
    
    int cell_count = 0;
    
    // 遍历矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] != 0 && !visited[i][j]) {
                // 发现一个新的细胞
                dfs(i, j);
                cell_count++;
            }
        }
    }
    
    // 输出细胞总数
    cout << cell_count << endl;
    
    return 0;
}
```


大佬题解
```cpp

#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//输入输出优化，请自动忽略
int n,m,ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1},a[105][105];//a即地图，dx和dy方向增量数组就不用我讲了吧
void dfs(int x,int y){
	if (x>n||y>m||x<0||y<0)return;
	a[x][y]=0;//标记为没有
	for (int i=0;i<4;i++)if (a[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜
}//搜索
int main(){
	read(n),read(m);
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)scanf("%1d",&a[i][j]);//只读1位
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)if (a[i][j])ans++,dfs(i,j);//找
	write(ans);//输出
	return 0;
}
```

求细胞数量dfs

# 迷宫寻路

## 题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 $n\times m$ 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 $(1, 1)$ 的位置，问能否走到 $(n, m)$ 位置。

## 输入格式

第一行，两个正整数 $n,m$。  

接下来 $n$ 行，输入这个迷宫。每行输入一个长为 $m$ 的字符串，`#` 表示墙，`.` 表示空地。

## 输出格式

仅一行，一个字符串。如果机器猫能走到 $(n, m)$，则输出 `Yes`；否则输出 `No`。

## 样例 #1

### 样例输入 #1

```
3 5
.##.#
.#...
...#.
```

### 样例输出 #1

```
Yes
```

## 提示

#### 样例解释

路线如下：$(1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5)$

#### 数据规模与约定 

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 100$，且 $(1,1)$ 和 $(n, m)$ 均为空地。


直接用bfd搜就好
```cpp
#include <iostream>
#include <queue>
using namespace std;

int n, m;
char maze[105][105];
bool visited[105][105];

// 方向数组，用于BFS遍历
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == '.' && !visited[x][y];
}

bool bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0}); // 从 (1, 1) 开始，但在数组中是 (0, 0)
    visited[0][0] = true;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        // 如果到达终点 (n, m)，返回 true
        if (x == n - 1 && y == m - 1) {
            return true;
        }

        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny)) {
                q.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }

    // 如果遍历完所有可能的路径都没有找到终点，返回 false
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> maze[i][j];
        }
    }

    if (bfs()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}
```

这种模板题目多练就好了

这题还能用dfs

```cpp
#include <iostream>
using namespace std;

int n, m;
char maze[105][105];
bool visited[105][105];

// 方向数组，用于DFS遍历
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool isValid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && maze[x][y] == '.' && !visited[x][y];
}

bool dfs(int x, int y) {
    // 如果到达终点 (n, m)，返回 true
    if (x == n && y == m) {
        return true;
    }

    visited[x][y] = true;

    // 遍历四个方向
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(nx, ny)) {
            if (dfs(nx, ny)) {
                return true;
            }
        }
    }

    // 如果遍历完所有可能的路径都没有找到终点，返回 false
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> maze[i][j];
        }
    }

    if (dfs(1, 1)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}
```


bfs迷宫模板题

一道几乎是模板dfs的题目  https://www.luogu.com.cn/problem/P1451


# 求细胞数量

## 题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

## 输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 `0` 到 `9` 的字符串，代表这个 $n \times m$ 的矩阵。

## 输出格式

一行一个整数代表细胞个数。

## 样例 #1

### 样例输入 #1

```
4 10
0234500067
1034560500
2045600671
0000000089
```

### 样例输出 #1

```
4
```

## 提示

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。

```cpp
#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> matrix;
vector<vector<bool>> visited;

// 方向数组，用于DFS遍历上下左右四个方向
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// DFS函数
void dfs(int x, int y) {
    visited[x][y] = true;
    
    // 遍历四个方向
    for (int i = 0; i < 4; ++i) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        
        // 检查是否越界，是否是细胞数字，是否未访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] != 0 && !visited[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    
    matrix.resize(n, vector<int>(m));
    visited.resize(n, vector<bool>(m, false));
    
    // 读取矩阵
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = row[j] - '0';
        }
    }
    
    int cell_count = 0;
    
    // 遍历矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] != 0 && !visited[i][j]) {
                // 发现一个新的细胞
                dfs(i, j);
                cell_count++;
            }
        }
    }
    
    // 输出细胞总数
    cout << cell_count << endl;
    
    return 0;
}
```
学习一下大佬们的代码（我也只有年纪比他们大），

```cpp
#include<bits/stdc++.h> 
using namespace std;
int n,m,ans=0;
int a[105][105];
bool used[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
	used[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(a[nx][ny]==0 || used[nx][ny]==1) continue;
		dfs(nx,ny);
	}
}
int main()
{
	cin>>n>>m;
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
			scanf("%1d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(used[i][j]==0 && a[i][j]!=0)
			{
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans;	
	return 0;
}
```
超简洁风
```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//输入输出优化，请自动忽略
int n,m,ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1},a[105][105];//a即地图，dx和dy方向增量数组就不用我讲了吧
void dfs(int x,int y){
	if (x>n||y>m||x<0||y<0)return;
	a[x][y]=0;//标记为没有
	for (int i=0;i<4;i++)if (a[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜
}//搜索
int main(){
	read(n),read(m);
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)scanf("%1d",&a[i][j]);//只读1位
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)if (a[i][j])ans++,dfs(i,j);//找
	write(ans);//输出
	return 0;
}
```




模板dfs

这是一道洛谷普及题https://www.luogu.com.cn/problem/P1109


# 学生分组

## 题目描述

有 $n$ 组学生，给出初始时每组中的学生个数，再给出每组学生人数的上界 $R$ 和下界 $L\ (L \le R)$，每次你可以在某组中选出一个学生把他安排到另外一组中，问最少要多少次才可以使 $N$ 组学生的人数都在 $[L,R]$ 中。

## 输入格式

第一行一个整数 $n$，表示学生组数；

第二行 $n$ 个整数，表示每组的学生个数；

第三行两个整数 $L,R$，表示下界和上界。

## 输出格式

一个数，表示最少的交换次数，如果不能满足题目条件输出 $-1$。

## 样例 #1

### 样例输入 #1

```
2
10 20
10 15
```

### 样例输出 #1

```
5
```

## 提示

### 数据范围及约定

对于全部数据，保证 $1\le n \le 50$。



思路是贪心，每次我们可以把某一个组的某个成员调到另一个组，想要让所有组都维持在l,r，最优解就是每次都从数量大于r的组调人去数量小于l的组就可以了，所以我们先计算所有大于r的组多出来的人（需要去掉这些人）,和小于l的少的人数，我们至少要从对应去掉或者补齐那么多人，那么到底多少人呢，之他们的最大值就行了

接下来就是不可能的情况也就是-1，很简单，就是所有人数加起来 < l * n,或者 > r * n


代码很简单

```cpp

#include <iostream>
using namespace std;
int n, l, r;
int a[101];

int b = 0,c = 0;

int cnt;
int main() {
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    cin >> l >> r;
    
    for(auto i = 0; i < n; i++) {
        if(a[i] < l) {
            b += (l - a[i]);
        }
        
        if(a[i] > r) {
            c += (a[i] - r);
        }
        
        cnt += a[i];
        
    }
    
    if(cnt < (l * n) || cnt > (r * n)) {
        cout << -1 << endl;
        return 0;
    }
    
    // cout << b << " " << c << endl;
    
    if(b > c) {
        cout << b << endl;
    }else{
        cout <<c << endl;
    }
    
}



```