devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

范围覆盖问题(Flood Fill)_小蓝负责一块区域的信号塔安装

作者：人工智能uu | 2024-07-04 13:19:26

赞

踩

小蓝负责一块区域的信号塔安装

范围覆盖问题(Flood Fill)

0.知识点

基本作用：寻找连通块
基本方法：BFS搜索
适用题目：需要找出分类块的题目/一些聚类问题
顾名思义，Flood Fill算法就是像洪水泛滥一样去寻找周围符合条件的区域，采用BFS可以完成先从自身最近的点寻找随后逐步扩展。

1.这本质上是一个搜索算法。作用是对一个图（二维数组）的所有的连通块进行操作

它是可以从其中一个点出发，扩展与这个点相邻的所有点（即一个等价类）

也就是说，给定连通块的所有的点，都可以把这个连通块上所有的点全部搜到

2.其中有三个参数：起始节点，目标节点的特征，要执行的处理

3.需要使用队列或者栈

4.分类可分为：四邻域填充（上下左右），八邻域填充法（加入对角线），基于扫描线填充方法

而实现方法又可以分为递归与非递归（基于栈）：

最简单的实现方法是采用深度优先搜索（dfs）的递归方法【大的区域填充可能导致栈溢出错误】

其次是采用广度优先搜索（bfs）的迭代来实现

最后是基于扫描线的算法，它实现了一种非递归的洪水填充算法。
除算出连通区域外，还可以应用于计算从某一节点开始，到可能到达其他所有节点的距离。
比如解决像走迷宫这类的问题。

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. int ans;
  7. int m,n;
  8. bool* visited;
  9. int dx[4] = {0, 1, 0, -1};//分别对应向上，向右，向下，向左
  10. int dy[4] = {1, 0, -1, 0};
  11.  
  12. void fun(int r,int c,const int num){
  13.     for(int i = 0; i<4; i++){
  14.         int newr = r+dx[i];
  15.         int newc = c+dy[i];
  16.         if(newr<0 || newr>m-1 || newc<0 || newc>n-1 || visited[newr*n+newc] || str[newr*n+newc]!=num)
  17.             continue;
  18.         visited[newr*n+newc] = true;
  19.         ans++;
  20.         fun(newr,newc,num);
  21.     }
  22. }
  23.  
  24.  
  25. int main(){
  26.     int cnt = 0;
  27.     int mlen = 0;
  28.     cin>>m>>n;
  29.     str = new int[m*n];
  30.     visited = new bool[m*n]();
  31.     for(int i=0; i<m; i++)
  32.         for(int j=0; j<n; j++){
  33.             scanf("%d",&str[i*n+j]);
  34.         }
  35.     for(int i=0; i<m; i++)
  36.         for(int j=0; j<n; j++){
  37.             if(!visited[i*n+j]){
  38.                 ans = 1;        //重置ans
  39.                 visited[i*n+j] = true; //不要忘记了把一开始进来的这个点的visited设置为true
  40.                 fun(i,j,str[i*n+j]);
  41.                 cout<< ans <<endl;
  42.                 if(mlen<ans) mlen = ans;//若新的这个点比之前的最大值还大则设置改制为最大值
  43.                 cnt++;
  44.             }
  45.         }
  46.     cout<<cnt<<endl;
  47.     cout<< mlen;
  48.     return 0;
  49. }
  50.  
  51.  
  52.  
  1. int bfs(PII start){
  2. 	queue<PII> q; // 宽搜用的队列
  3. 	
  4. 	q.push(start); // 宽搜入队
  5. 	memset(vis, 0, sizeof(vis)); // 对数组进行清空，表示所有点暂时还没有到达过
  6. 	vis[start.x][start.y] = 1; // 起点是肯定来过的
  7. 	
  8. 	int dx[4] = {-1,0,1,0}; // 坐标偏移量数组
  9.     int dy[4] = {0,1,0,-1};
  10. 	
  11. 	while(!q.empty()){
  12. 		PII f = q.front(); // 取出队头
  13. 		q.pop(); // 弹出队头元素
  14. 		
  15. 		for(int i = 0; i < 4; i++){ // 对现在得到的坐标的上下左右四个方向的偏移的各个位置的状况进行查看及操作
  16. 			int x = f.x + dx[i]; // 各个方向上的坐标
  17. 			int y = f.y + dy[i]; 
  18. 			
  19. 			if(x < 0 || x >= w || y < 0 || y >= h) continue; // 防止越界
  20. 			if(mapp[x][y] == '#') continue; // 如果是障碍物就退出
  21. 			if(vis[x][y]) continue; // 遍历过就退出，防止二次统计
  22.             
  23. 			vis[x][y] = 1; // 我这时候已经来过这个点了
  24. 			q.push({x, y});	 // 压入队列，后期再看这个点的其他点
  25. 		}
  26. 	}
  27. 	
  28. 	return *; // 可能要返回值
  29. }


 

1.清理水草


小蓝有一个 n * m 大小的矩形水域，小蓝将这个水域划分为 n 行 m 列，行数从 1 到 n 标号，列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。

　　现在，这个水域长满了水草，小蓝要清理水草。

　　每次，小蓝可以清理一块矩形的区域，从第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。

　　经过一段时间清理后，请问还有多少地方没有被清理过。

输入格式

　　输入第一行包含两个整数 n, m，用一个空格分隔。

　　第二行包含一个整数 t ，表示清理的次数。

　　接下来 t 行，每行四个整数 r1, c1, r2, c2，相邻整数之间用一个空格分隔，表示一次清理。请注意输入的顺序。

输出格式

　　输出一行包含一个整数，表示没有被清理过的面积。

样例输入

2 3

2

1 1 1 3

1 2 2 2

样例输出

2

样例输入

30 20

2

5 5 10 15

6 7 15 9

样例输出

519

评测用例规模与约定

对于所有评测用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。
 

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int n,m,t;
  8.     cin>>n>>m;
  9.     cin>>t;
  10.     int r1,c1,r2,c2;
  11.     int area[100][100] = {0};
  12.     for(int i=0;i<t;i++){
  13.         cin>>r1>>c1>>r2>>c2;
  14.         for(int j=r1-1;j<r2;j++)
  15.             for(int k=c1-1;k<c2;k++)
  16.                 area[j][k] = 1;
  17.     }
  18.     int sum = 0;
  19.     for(int j=0;j<n;j++)
  20.             for(int k=0;k<m;k++)
  21.                 if(area[j][k]==0) sum++;
  22.     cout<< sum;
  23.     return 0;
  24. }

核心思想是（涂色）

先用一个area【100】【100】 =  { 0 }；来制作一张白布

然后再用几个循环来给白布上的 单位块 赋值（重复赋值也无所谓）

最后再检查有哪些单位块被染色了

2.信号覆盖


小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (0, 0)， 东南角坐标为 (W, 0)， 西北角坐标为 (0, H)， 东北角坐标为 (W, H)。其中 W, H 都是整数。

　　他在 n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R 的圆形（包括边缘）。

　　为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 到 W，纵坐标范围为 0 到 H，总共测试 (W+1) * (H+1) 个点。

　　给定信号塔的位置，请问这 (W+1)*(H+1) 个点中有多少个点被信号覆盖。

输入格式

　　输入第一行包含四个整数 W, H, n, R，相邻整数之间使用一个空格分隔。

　　接下来 n 行，每行包含两个整数 x, y，表示一个信号塔的坐标。信号塔可能重合，表示两个信号发射器装在了同一个位置。

输出格式

　　输出一行包含一个整数，表示答案。

样例输入

10 10 2 5

0 0

7 0

样例输出

57

评测用例规模与约定

对于所有评测用例，1 <= W, H <= 100，1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H
 

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int W,H,n,R;
  8.     cin>>W>>H>>n>>R;
  9.     int x,y;
  10.     int area[101][101] = {0};
  11.     for(int i=0;i<n;i++){
  12.         cin>>x>>y;
  13.         for(int j=0;j<=W;j++)
  14.             for(int k=0;k<=H;k++)
  15.                 if((x-j)*(x-j)+(y-k)*(y-k)<=R*R) area[j][k] = 1;
  16.     }
  17.     int sum = 0;
  18.     for(int j=0;j<=W;j++)
  19.             for(int k=0;k<=H;k++)
  20.                 if(area[j][k]==1) sum++;
  21.     cout<< sum;
  22.     return 0;
  23. }

核心思想：对于每一个圆圈，用两个循环遍历白布，距离小于等于半径的就涂色

改进：每次都要遍历整张白布，存在很大的浪费

将每次检查的范围限定在正好框住⚪的一个最小正方形中即可

这里用max（）与min（）函数来防止正方形截取到边界以外的内容

注意：y代表行，在外循环（对应的是j）；x代表列，在内循环（对应的是x)

然后x_l与x_f，还有y_up与y_down的位置关系，哪个放左边，哪个放右边

(x-k)*(x-k) 不是（y-k）*（y-k）！！！

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int W,H,n,R;
  8.     cin>>W>>H>>n>>R;
  9.     int x,y;
  10.     int area[101][101] = {0};
  11.     for(int i=0;i<n;i++){
  12.         cin>>x>>y;
  13.         int x_l = max(0,x-R);
  14.         int x_r = min(W,x+R);
  15.         int y_up = min(H,y+R);
  16.         int y_down = max(0,y-R);
  17.         for(int j=y_down;j<=y_up;j++)
  18.             for(int k=x_l;k<=x_r;k++)
  19.                 if((y-j)*(y-j)+(x-k)*(x-k)<=R*R) area[j][k] = 1;
  20.     }
  21.     int sum = 0;
  22.     for(int j=0;j<=W;j++)
  23.             for(int k=0;k<=H;k++)
  24.                 if(area[j][k]==1) sum++;
  25.     cout<< sum;
  26.     return 0;
  27. }

3.最大连通分块

小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1 。

　   110010000011111110101001001001101010111011011011101001111110
　　010000000001010001101100000010010110001111100010101100011110
　　001011101000100011111111111010000010010101010111001000010100
　　101100001101011101101011011001000110111111010000000110110000
　　010101100100010000111000100111100110001110111101010011001011
　　010011011010011110111101111001001001010111110001101000100011
　　101001011000110100001101011000000110110110100100110111101011
　　101111000000101000111001100010110000100110001001000101011001
　　001110111010001011110000001111100001010101001110011010101110
　　001010101000110001011111001010111111100110000011011111101010
　　011111100011001110100101001011110011000101011000100111001011
　　011010001101011110011011111010111110010100101000110111010110
　　001110000111100100101110001011101010001100010111110111011011
　　111100001000001100010110101100111001001111100100110000001101
　　001110010000000111011110000011000010101000111000000110101101
　　100100011101011111001101001010011111110010111101000010000111
　　110010100110101100001101111101010011000110101100000110001010
　　110101101100001110000100010001001010100010110100100001000011
　　100100000100001101010101001101000101101000000101111110001010
　　101101011010101000111110110000110100000010011111111100110010
　　101111000100000100011000010001011111001010010001010110001010
　　001010001110101010000100010011101001010101101101010111100101
　　001111110000101100010111111100000100101010000001011101100001
　　101011110010000010010110000100001010011111100011011000110010
　　011110010100011101100101111101000001011100001011010001110011
　　000101000101000010010010110111000010101111001101100110011100
　　100011100110011111000110011001111100001110110111001001000111
　　111011000110001000110111011001011110010010010110101000011111
　　011110011110110110011011001011010000100100101010110000010011
　　010011110011100101010101111010001001001111101111101110011101
 

　　如果从一个标为 1 的位置可以通过上下左右的1走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。

请问矩阵中最大的连通分块有多大？   （其实是一条数链树，既不是一个矩阵块，也不是一条无分支的线。。。）

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int str[30][60] = {0};
  6. int ans;
  7. int m,n;
  8.  
  9. void fun(int r,int c){
  10.  
  11.     str[r][c] = 0; //这样的话相当于把走过的全部抹去了。类似于等价类的思想
  12.  
  13.     //如果可以向下走，那就再看下移一个的位置能不能再走，都走不了了就回头
  14.     if(r-1>=0 && str[r-1][c]==1){
  15.             ans++;
  16.             fun(r-1,c);
  17.     }
  18.    
  19.     //如果可以向上走，那就再看上移一个的位置能不能再走，都走不了了就回头
  20.     if(r+1<m && str[r+1][c]==1){
  21.             ans++;
  22.             fun(r+1,c);
  23.     }
  24.  
  25.     //如果可以向左走，那就再看左移一个的位置能不能再走，都走不了了就回头
  26.     if(c-1>=0 && str[r][c-1]==1){
  27.             ans++;
  28.             fun(r,c-1);
  29.     }
  30.  
  31.     //如果可以向右走，那就再看右移一个的位置能不能再走，都走不了了就回头
  32.     if(c+1<n && str[r][c+1]==1){
  33.             ans++;
  34.             fun(r,c+1);
  35.     }
  36. }
  37.  
  38.  
  39. int main()
  40. {
  41.     int mlen = 0;
  42.     cin>>m>>n;
  43.     int *str = new int(m*n);
  44.     for(int i=0;i<m;i++)
  45.         for(int j=0;j<n;j++){
  46.             scanf("%1d",str+i*n+j);
  47.         }
  48.     for(int i=0;i<m;i++)
  49.         for(int j=0;j<m;j++){
  50.             if(str[i*n+j]==1){
  51.                 ans = 1;        //重置ans
  52.                 fun(i,j);
  53.                 if(mlen<ans) mlen = ans;  //若新的这个点比之前的最大值还大则设置改制为最大值
  54.             }
  55.     }
  56.     cout<< mlen;
  57.     return 0;
  58. }

核心思想是：

        递归操作，由于向上下左右移动后的情况，只是位置不变，而对于四个方向的操作还是一样所以可以来利用递归思想，与dfs算法是类似的

优化：！！！

         str[ r ][ c ] = 0;  这样的话相当于把走过的数全部抹去了。类似于等价类的思想

极大的减少了遍历与递归的次数（既不用往回跑了，也不用重复计算等价的联通分块了）！！！

并且确保走过的不会被再走一次，形成了无限循环的死圈

  1. #include <iostream>
  2. #include <sstream>
  3. #include<vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7. string *matrix;
  8. int temp;
  9.  
  10. void dfs(int x, int y) {
  11.     if (x < 0 || y < 0 || x > 29 || y > 59 || matrix[x][y] == '0') return;
  12.     matrix[x][y] = '0';
  13.     temp++;
  14.     dfs(x - 1, y);
  15.     dfs(x + 1, y);
  16.     dfs(x, y - 1);
  17.     dfs(x, y + 1);
  18. }
  19.  
  20.  
  21. int main() {
  22.     freopen("data.txt", "r", stdin); // 这里用文件传入大型数据
  23.     matrix = new string[30];
  24.     for (int i = 0; i < 30; i++) {
  25.         cin >> matrix[i];
  26.     }
  27.     int ans = 0;
  28.     for (int i = 0; i < 30; i++) {
  29.         for (int j = 0; j < 60; j++) {
  30.             if (matrix[i][j] == '1') {
  31.                 temp = 0;
  32.                 dfs(i, j);
  33.                 ans = max(ans, temp);
  34.             }
  35.         }
  36.     }
  37.     cout << ans << endl;
  38.     return 0;
  39. }
  40.  
  41.

连通分块变式题目

编写程序，读入矩阵行数、列数及所有矩阵元素，矩阵中所有元素均为正整数，计算并打印出矩阵中的最大连通块数。

注：如果两个元素值相同，并且上、下、左、右四个方向之一相邻，则称两个元素是连通的

连通关系是可传递的，一个元素的连通元素，也是与它连通元素的连通元素

最大连通块定义为所有连通元素组成的最大集，单个元素也可成为最大连通块

要求设计出求连通块数的递归或非递归算法

矩阵行数、列数不超出100

输入格式:
行数、列数及所有矩阵元素，所有数据均为整型。

输入样例：

7 6     
4   4   4   4   4   4 
4   1   3   2   1   4 
4   1   2   2   1   4 
4   1   1   1   1   4 
4   1   2   2   3   4 
4   3   3   3   3   4 
4   4   4   4   4   4 

输出格式:

（1）每个联通分块对应的大小

（2）连通块数量

（3）最大连通分块数

输出样例：

22
9
1
3
2
5
6
22

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. int ans;
  7. int m,n;
  8.  
  9. void fun(int r,int c,const int num)
  10. {
  11.  
  12.     str[r*n+c] = 0; //这样的话相当于把走过的全部抹去了。类似于等价类的思想
  13.  
  14.     //如果可以向下走，那就再看下移一个的位置能不能再走，都走不了了就回头
  15.     if(r-1>=0 && str[(r-1)*n+c]==num)
  16.     {
  17.         ans++;
  18.         fun(r-1,c,num);
  19.     }
  20.  
  21.     //如果可以向上走，那就再看上移一个的位置能不能再走，都走不了了就回头
  22.     if(r+1<m && str[(r+1)*n+c]==num)
  23.     {
  24.         ans++;
  25.         fun(r+1,c,num);
  26.     }
  27.  
  28.     //如果可以向左走，那就再看左移一个的位置能不能再走，都走不了了就回头
  29.     if(c-1>=0 && str[r*n+c-1]==num)
  30.     {
  31.         ans++;
  32.         fun(r,c-1,num);
  33.     }
  34.  
  35.     //如果可以向右走，那就再看右移一个的位置能不能再走，都走不了了就回头
  36.     if(c+1<n && str[r*n+c+1]==num)
  37.     {
  38.         ans++;
  39.         fun(r,c+1,num);
  40.     }
  41. }
  42.  
  43.  
  44. int main()
  45. {
  46.     int cnt = 0;
  47.     int mlen = 0;
  48.     cin>>m>>n;
  49.     str = new int[m*n];
  50.     for(int i=0; i<m; i++)
  51.         for(int j=0; j<n; j++) {
  52.             scanf("%d",&str[i*n+j]);
  53.         }
  54.     for(int i=0; i<m; i++)
  55.         for(int j=0; j<n; j++){
  56.             if(str[i*n+j]){
  57.                 ans = 1;        //重置ans
  58.                 fun(i,j,str[i*n+j]);
  59.                 cout<< ans <<endl;
  60.                 if(mlen<ans) mlen = ans;//若新的这个点比之前的最大值还大则设置改制为最大值
  61.                 cnt++;
  62.             }
  63.         }
  64.     cout<< cnt <<endl;
  65.     cout<< mlen;
  66.     return 0;
  67. }

（变化，不只是0  和  1的问题了，而是相邻的数字是否相等的问题）

优化另解：

实际上可以用一个visited数组来防止走回头路

然后上下左右移动的四种情况也可以统一格式书写，减少代码量

用两个数组分别存储对x和对y的位移量

再用一个for循环遍历并讨论

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. int ans;
  7. int m,n;
  8. bool* visited;
  9. int dx[4] = {0, 1, 0, -1};//分别对应向上，向右，向下，向左
  10. int dy[4] = {1, 0, -1, 0};
  11.  
  12. void fun(int r,int c,const int num){
  13.     for(int i = 0; i<4; i++){
  14.         int newr = r+dx[i];
  15.         int newc = c+dy[i];
  16.         if(newr<0 || newr>m-1 || newc<0 || newc>n-1 || visited[newr*n+newc] || str[newr*n+newc]!=num)
  17.             continue;
  18.         visited[newr*n+newc] = true;
  19.         ans++;
  20.         fun(newr,newc,num);
  21.     }
  22. }
  23.  
  24.  
  25. int main(){
  26.     int cnt = 0;
  27.     int mlen = 0;
  28.     cin>>m>>n;
  29.     str = new int[m*n];
  30.     visited = new bool[m*n]();
  31.     for(int i=0; i<m; i++)
  32.         for(int j=0; j<n; j++){
  33.             scanf("%d",&str[i*n+j]);
  34.         }
  35.     for(int i=0; i<m; i++)
  36.         for(int j=0; j<n; j++){
  37.             if(!visited[i*n+j]){
  38.                 ans = 1;        //重置ans
  39.                 visited[i*n+j] = true; //不要忘记了把一开始进来的这个点的visited设置为true
  40.                 fun(i,j,str[i*n+j]);
  41.                 cout<< ans <<endl;
  42.                 if(mlen<ans) mlen = ans;//若新的这个点比之前的最大值还大则设置改制为最大值
  43.                 cnt++;
  44.             }
  45.         }
  46.     cout<<cnt<<endl;
  47.     cout<< mlen;
  48.     return 0;
  49. }

4.最长滑行


        小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。

　　如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。

　　如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。

　　小蓝不能滑出矩阵所表示的场地。

　　小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。

输入格式

　　输入第一行包含两个整数 n, m，用一个空格分隔。

　　接下来 n 行，每行包含 m 个整数，相邻整数之间用一个空格分隔，依次表示每个位置的高度。

输出格式

　　输出一行包含一个整数，表示答案。

样例输入

4 5 

1 4 6 3 1 

11 8 7 3 1 

9 4 5 2 1 

1 3 2 2 1 

样例输出

7

样例输入

5 5 
1 2 3 4 5 
16 17 18 19 6 
15 24 25 20 7 
14 23 22 21 8 
13 12 11 10 9 

输出样例

25

样例说明

　　滑行的位置一次为 (2, 1), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2), (4, 3)。

！！！不能回头走，必须一条路走到底

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. int ans;
  7. int m,n;
  8. int dx[4] = {0, 1, 0, -1};//分别对应向上，向右，向下，向左
  9. int dy[4] = {1, 0, -1, 0};
  10.  
  11. void fun(int r,int c,int step)
  12. {
  13.     for(int i = 0; i<4; i++)
  14.     {
  15.         if(ans < step) ans = step;  //!!!
  16.         int newr = r+dx[i];
  17.         int newc = c+dy[i];
  18.         if(newr<0 || newr>m-1 || newc<0 || newc>n-1 || str[newr*n+newc] >= str[r*n+c] )
  19.             continue;
  20.         fun(newr,newc,step+1);  //!!!
  21.     }
  22. }
  23.  
  24.  
  25. int main()
  26. {
  27.     int mlen = 0;
  28.     cin>>m>>n;
  29.     str = new int[m*n];
  30.     for(int i=0; i<m; i++)
  31.         for(int j=0; j<n; j++){
  32.             scanf("%d",&str[i*n+j]);
  33.         }
  34.     for(int i=0; i<m; i++)
  35.         for(int j=0; j<n; j++){
  36.                 ans = 1;    //重置ans
  37.                 fun(i,j,1);
  38.                 if(mlen<ans) mlen = ans;//若新的这个点比之前的最大值还大则设置改制为最大值
  39.         }
  40.     cout<< mlen;
  41.     return 0;
  42. }

核心思想：一条路走到底，且要找出同一起点中的最长路径

再比较不同起点的最长路径的长度，选择最长的那条

这里就要用到一个中间变量 step 每次移动位置时都会创造一个新的step

栈中不同的递归函数之间的step是不同的，且相互不影响（实参的传递本质上是传入一个副本）

所以如果用dfs算法，一条路走到底了再退回栈，当前的递归函数中的step还是对的

不能用一个全局变量ans，会互相影响，导致错误

且如果存在step大于ans的情况则立刻更新

5.池塘计数(简单套用)


农夫约翰有一片 N∗M 的矩形土地。最近，由于降雨的原因，部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入样例
10 12

  1. W........WW.
  2. .WWW.....WWW
  3. ....WW...WW.
  4. .........WW.
  5. .........W..
  6. ..W......W..
  7. .W.W.....WW.
  8. W.W.W.....W.
  9. .W.W......W.
  10. ..W.......W.

输出样例
3

dfs版本

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. char *str = NULL;
  6. bool* visited;
  7.  
  8. int ans;
  9. int m,n;
  10.  
  11. int dx[8] = {0, 1, 0, -1, 1, -1, 1, -1};//分别对应八个方位
  12. int dy[8] = {1, 0, -1, 0, 1, 1, -1, -1};
  13.  
  14. void fun(int r,int c,const char num){
  15.     visited[r*n+c] = true; //不要忘记了把一开始进来的这个点的visited设置为true
  16.     for(int i = 0; i<8; i++){
  17.         int newr = r+dx[i];
  18.         int newc = c+dy[i];
  19.  
  20.         if(newr<0 || newr>m-1 || newc<0 || newc>n-1 || visited[newr*n+newc] || str[newr*n+newc]!=num)
  21.             continue;
  22.  
  23.         visited[newr*n+newc] = true;
  24.         ans++;
  25.         fun(newr,newc,num);
  26.     }
  27. }
  28.  
  29.  
  30. int main(){
  31.     int cnt = 0;
  32.     int mlen = 0;
  33.     cin>>m>>n;
  34.     str = new char[m*n];
  35.     visited = new bool[m*n]();
  36.  
  37.     for(int i=0; i<m; i++)
  38.         for(int j=0; j<n; j++){
  39.             cin>>str[i*n+j];
  40.         }
  41.  
  42.     for(int i=0; i<m; i++)
  43.         for(int j=0; j<n; j++){
  44.             if(!visited[i*n+j] && str[i*n+j] == 'W'){
  45.                 ans = 1;        //重置ans
  46.                 fun(i,j,str[i*n+j]);
  47.                 if(mlen<ans) mlen = ans;//若新的这个点比之前的最大值还大则设置改制为最大值
  48.                 cnt++;
  49.             }
  50.         }
  51.  
  52.     cout<<cnt<<endl;
  53.     cout<< mlen;
  54.     return 0;
  55. }

bfs版本（加上了队列+pair+PII）

  1. #include <iostream>
  2. #include <queue>
  3.  
  4. #define x first
  5. #define y second
  6.  
  7. using namespace std;
  8.  
  9. typedef pair<int, int> PII;
  10.  
  11. const int N = 1010;
  12.  
  13. int n, m;
  14. char g[N][N];
  15. bool visited[N][N];
  16. int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
  17. int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};//八个方向
  18.  
  19. void bfs(int x, int y)
  20. {
  21.     visited[x][y] = true;
  22.  
  23.     queue<PII> q;
  24.     q.push({x, y});
  25.  
  26.     while(q.size())
  27.     {
  28.         PII tmp = q.front();
  29.         q.pop();
  30.  
  31.         for(int i = 0; i < 8; i++)
  32.         {
  33.             int nx = tmp.x + dx[i], ny = tmp.y + dy[i];
  34.  
  35.             if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  36.  
  37.             if(visited[nx][ny] || g[nx][ny] == '.') continue;
  38.  
  39.             visited[nx][ny] = true;
  40.             
  41.             q.push({nx, ny});
  42.         }
  43.     }
  44. }
  45.  
  46. int main()
  47. {
  48.     cin >> n >> m;
  49.     for(int i = 0; i < n; i++) cin >> g[i];
  50.  
  51.     int ans = 0;
  52.     for(int i = 0; i < n; i++)
  53.     {
  54.         for(int j = 0; j < m; j++)
  55.         {
  56.             if(g[i][j] == 'W' && !visited[i][j])
  57.             {
  58.                 bfs(i, j);
  59.                 ans ++;
  60.             }
  61.         }
  62.     }
  63.  
  64.     cout << ans << endl;
  65.  
  66.     return 0;
  67. }

6.请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。

城堡被分割成 m∗n个方格区域，每个方格区域可以有0~4面墙。
城堡描述如下：

  1.     1   2   3   4   5   6   7  
  2.    #############################
  3.  1 #   |   #   |   #   |   |   #
  4.    #####---#####---#---#####---#
  5.  2 #   #   |   #   #   #   #   #
  6.    #---#####---#####---#####---#
  7.  3 #   |   |   #   #   #   #   #
  8.    #---#########---#####---#---#
  9.  4 #   #   |   |   |   |   #   #
  10.    #############################
  11.            (图 1)
  12.    #  = Wall   
  13.    |  = No wall
  14.    -  = No wall
  15.    方向：上北下南左西右东。

输入格式：

第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。

接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。

例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。

城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。

输入的数据保证城堡至少有两个房间。

输出格式：

共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
数据范围
1≤m,n≤50,0≤P≤15

输入样例：
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 

输出样例：
5
9
 

注意点：

1.这里用 1,2,4,8 来表示西、北、东、南，

其实就是用二进制来表示，1代表有这面墙，0代表没有

然后其实也可以用什么1,3,9,27，只是效率没那么高，本质还是一样的

这里就涉及怎么通过数字的和来反推有哪些数

比如11 = 1 + 2 + 8表示西、北、南有墙

在这个位置上就只能向东走，换而言之，就是给定一个四位的二进制数

对应位为0才能够向该方向出发，求连通块的数目以及最大连通块的面积

2.要注意的易错点就是虽然上北下南左西右东，但是地图上的上面对应的是(-1,0)，

表示横坐标的减少，而不是我们经常用到的(0,1)表示上面

因为这里是行列（0，-1），（-1，0），（0，1），（1，0）分别表示西北东南四个方向

比如某个位置上的数是1010，就是南和北可以走，就可以向（0，-1）和（0，1）移动

3.由于还要找出最大的房间，所以BFS函数要返回一个int值 【ans】

我们可以在队列循环开始时就将空间大小加一即可

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. bool* visited;
  7.  
  8. int ans;
  9. int m,n;
  10.  
  11. int dx[4] = {0, -1, 0, 1};//分别对应四个方位：向西、向北、向东、向南
  12. int dy[4] = {-1, 0, 1, 0};
  13.  
  14. void Trans(int n,int *Access){
  15.     int i = 0;
  16.     while(i!=4){
  17.         Access[i++] = n%2;
  18.         n /= 2;
  19.     }
  20. }
  21.  
  22. //用于解码数字代表的信息：从0到3依次是——西、北、东、南
  23.  
  24. void fun(int r,int c){
  25.     visited[r*n+c] = true; //不要忘记了把一开始进来的这个点的visited设置为true
  26.     int Access[4] = {0}; //这里要和上面的dx，dy一一对应
  27.  
  28.     Trans(str[r*n+c],Access);
  29.  
  30.     for(int i = 0; i<4; i++){
  31.         int newr = r+dx[i];
  32.         int newc = c+dy[i];
  33.  
  34.         if(newr<0 || newr>m-1 || newc<0 || newc>n-1 )
  35.             continue;
  36.  
  37.         if(visited[newr*n+newc] || Access[i])
  38.             continue;
  39.  
  40.         visited[newr*n+newc] = true;
  41.         ans++;
  42.         fun(newr,newc);
  43.     }
  44. }
  45.  
  46.  
  47.  
  48. int main(){
  49.     int cnt = 0;
  50.     int mlen = 0;
  51.     cin>>m>>n;
  52.     str = new int[m*n];
  53.     visited = new bool[m*n]();
  54.  
  55.     for(int i=0; i<m; i++)
  56.         for(int j=0; j<n; j++){
  57.             cin>>str[i*n+j];
  58.         }
  59.  
  60.     for(int i=0; i<m; i++)
  61.         for(int j=0; j<n; j++){
  62.             if(!visited[i*n+j]){
  63.                 ans = 1;        //重置ans
  64.                 fun(i,j);
  65.                 cout<<ans<<endl;
  66.                 if(mlen<ans) mlen = ans;//若新的这个点比之前的最大值还大则设置改制为最大值
  67.                 cnt++;
  68.             }
  69.         }
  70.  
  71.     cout<<cnt<<endl;
  72.     cout<<mlen;
  73.     return 0;
  74. }

还有一个要特别注意的是：

Access【】数组必须要设置成在递归函数fun【】内的局部变量，随着递归函数变动，且回退时也要用到原来的数组！！！
 

另解——用bfs实现的：

  1. #include <bits/stdc++.h>
  2.  
  3. #define x first
  4. #define y second
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> PII;
  9.  
  10. const int N = 55;
  11.  
  12. int n, m;
  13. int g[N][N];
  14. bool st[N][N];
  15. int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
  16.  
  17. int bfs(int x, int y)
  18. {
  19.     int res = 0;//记录房间大小
  20.     st[x][y] = true;
  21.  
  22.     queue<PII> q;
  23.     q.push({x, y});
  24.  
  25.     while(q.size())
  26.     {
  27.         PII tmp = q.front();
  28.         q.pop();
  29.         res ++;
  30.  
  31.         for(int i = 0; i < 4; i++)
  32.         {
  33.             if(g[tmp.x][tmp.y] >> i & 1) continue;
  34.             int nx = tmp.x + dx[i], ny = tmp.y + dy[i];
  35.  
  36.             if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  37.             if(st[nx][ny]) continue;
  38.  
  39.             st[nx][ny] = true;
  40.             q.push({nx, ny});
  41.         }
  42.     }
  43.  
  44.     return res;
  45. }
  46.  
  47. int main()
  48. {
  49.     cin >> n >> m;
  50.     for(int i = 0; i < n; i++)
  51.         for(int j = 0; j < m; j++)
  52.             cin >> g[i][j];
  53.  
  54.     int ans = 0, num = 0;
  55.     for(int i = 0; i < n; i++)
  56.         for(int j = 0; j < m; j++)
  57.         {
  58.             if(!st[i][j])
  59.             {
  60.                 num ++;//房间数目
  61.                 int t = bfs(i, j);
  62.                 ans = max(ans, t);
  63.             }            
  64.         }
  65.  
  66.     cout << num << endl;
  67.     cout << ans << endl;
  68.  
  69.     return 0;
  70. }

技巧：

用到到二进制转换的技巧：num >> x & 1 可以判断，num二进制的第x位是否为1
同理：（num >> x & 1）判断是不是0

7.山峰和山谷

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n×n 的网格，每个格子 (i，j) 的高度 w(i，j)

是给定的。若两个格子有公共顶点，那么它们就是相邻的格子.

如与 (i，j) 相邻的格子有(i−1，j−1)，(i−1，j)，(i−1，j+1)，(i，j−1)，(i，j+1)，(i+1，j−1)，(i+1，j)，(i+1，j+1)。

我们定义一个格子的集合 S 为山峰（山谷）当且仅当：

S 的所有格子都有相同的高度。
S 的所有格子都连通。
对于 s 属于 S，与 s 相邻的 s′ 不属于 S，都有 ws>ws′（山峰），或者 ws< ws′（山谷）。
如果周围不存在相邻区域，则同时将其视为山峰和山谷。
你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入：

第一行包含一个正整数 n，表示地图的大小。接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。

输出：

共一行，包含两个整数，表示山峰和山谷的数量。
数据范围
1 ≤ n ≤ 1000
0 ≤ w ≤ 10^9
输入样例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 
输出样例1：
2 1
输入样例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 
输出样例2：
3 3

核心思想：在搜索连通块的时候需要判断周围连通块的类型，并且由题可知，这个图是由山峰和山

谷组成的，一个点要么是山峰要么就是山谷！！！（气死我了，这句话错得离谱）所以要一次性检查完山峰和山谷

同时由于所有点都相等时，算作即是山峰，也是山谷，所以需要额外加点判断操作

然后如果high和low都有标记时，视为既不是山峰也不是山谷

可以使用两个变量记录当前连通块周围是否有比它高或者比它矮的连通块

我们可以使用flood fill算法搜索连通块，根据两个记录的变量计算当前山峰和山谷的数量。

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. bool* visited;
  7.  
  8. int ans;
  9. int n;
  10.  
  11. int dx[8] = {0, -1, 0, 1, 1, 1, -1, -1};
  12. int dy[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
  13.  
  14. bool high = false;
  15. bool low = false;
  16.  
  17. void fun(int r,int c)
  18. {
  19.  
  20.     visited[r*n+c] = true;
  21.  
  22.     for(int i = 0; i<8; i++)
  23.     {
  24.         int newr = r+dx[i];
  25.         int newc = c+dy[i];
  26.  
  27.         if(newr<0 || newr>n-1 || newc<0 || newc>n-1 )
  28.             continue;
  29.  
  30.         if(str[r*n+c]!=str[newr*n+newc])
  31.         {
  32.             if(str[r*n+c]>str[newr*n+newc]) high = true;
  33.             else low = true;
  34.         }
  35.         else
  36.         {
  37.             if(visited[newr*n+newc])
  38.                 continue;
  39.             visited[newr*n+newc] = true;
  40.             ans++;
  41.             fun(newr,newc);
  42.         }
  43.     }
  44. }
  45.  
  46.  
  47. int main()
  48. {
  49.     int cnt = 0;
  50.     int num = 0;
  51.     cin>>n;
  52.     str = new int[n*n];
  53.     visited = new bool[n*n]();
  54.  
  55.     for(int i=0; i<n; i++)
  56.         for(int j=0; j<n; j++)
  57.         {
  58.             cin>>str[i*n+j];
  59.         }
  60.  
  61.     for(int i=0; i<n; i++)
  62.         for(int j=0; j<n; j++)
  63.         {
  64.             if(!visited[i*n+j])
  65.             {
  66.                 ans = 1; //重置ans和high,low
  67.                 high = false;
  68.                 low = false;
  69.  
  70.                 fun(i,j);
  71.                 cout<<ans<<endl;
  72.  
  73.                 if(low && high) continue;
  74.                 else if(high) cnt++;
  75.                 else if(low) num++;
  76.                 else
  77.                 {
  78.                     cnt++;
  79.                     num++;
  80.                 }
  81.             }
  82.         }
  83.  
  84.     cout<<"Mountains:"<<cnt<<endl;
  85.     cout<<"Valleys:"<<num<<endl;
  86.     return 0;
  87. }

用bfs

  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 1005;
  7. typedef pair<int,int> PII;
  8. int g[N][N],n,res1 = 0,res2 = 0;
  9. int dx[] = {0,0,-1,1,-1,-1,1,1};
  10. int dy[] = {1,-1,0,0,-1,1,-1,1};
  11. bool st[N][N];
  12. PII q[N * N];
  13.  
  14. void bfs(int x,int y){
  15.     int hh = 0,tt = 0;
  16.     q[0] = {x,y};
  17.     st[x][y] = true;
  18.     bool flag1 = true,flag2 = true;
  19.     while(hh <= tt){
  20.         PII t = q[hh++];
  21.         for(int i = 0;i < 8;i++){
  22.             int nx = t.first + dx[i],ny = t.second + dy[i];
  23.             if(nx < 0 || nx >= n || ny < 0 || ny >= n)  continue;
  24.             if(g[nx][ny] != g[t.first][t.second]){
  25.                 if(g[nx][ny] < g[t.first][t.second])    flag2 = false;
  26.                 else    flag1 = false;
  27.             }
  28.             else if(!st[nx][ny]){
  29.                 q[++tt] = {nx,ny};
  30.                 st[nx][ny] = true;
  31.             }
  32.         }
  33.     }
  34.     if(flag1)   res1++;
  35.     if(flag2)   res2++;
  36. }
  37. int main(){
  38.     scanf("%d",&n);
  39.     for(int i = 0;i < n;i++){
  40.         for(int j = 0;j < n;j++){
  41.             scanf("%d",&g[i][j]);
  42.         }
  43.     }
  44.     for(int i = 0;i < n;i++){
  45.         for(int j = 0;j < n;j++){
  46.             if(!st[i][j])   bfs(i,j);
  47.         }
  48.     }
  49.     printf("%d %d\n",res1,res2);
  50.     return 0;
  51. }

8.迷宫问题

给定一个M*N 的迷宫图、入口与出口、行走规则。求一条最短的从指定入口到出口的路径,所求路径必须是简单路径，即路径不重复 (为了方便算法起见，在整个迷宫外围加上一堵墙）

输入：

  1. 8 8 
  2. 0 0 1 0 0 0 1 0  
  3. 0 0 1 0 0 0 1 0  
  4. 0 0 0 0 1 1 0 0 
  5. 0 1 1 1 0 0 0 0 
  6. 0 0 0 1 0 0 0 0
  7. 0 1 0 0 0 1 0 0 
  8. 0 1 1 1 0 1 1 0 
  9. 1 0 0 0 0 0 0 0 

输出：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int *str = NULL;
  6. bool* visited;
  7.  
  8. int ans;
  9. int m,n;
  10. int rout[100][2];
  11. bool flag = false;
  12.  
  13. int dx[4] = {0, -1, 0, 1};
  14. int dy[4] = {-1, 0, 1, 0};
  15.  
  16. //定义：用1来覆盖0，从而达到封掉死路的效果
  17.  
  18. void fun(int r,int c)
  19. {
  20.     int i;
  21.     while(!flag)
  22.     {
  23.         if(r == m && c == n)  flag = true;
  24.  
  25.         visited[r*n+c] = true;
  26.  
  27.         rout[ans-1][0] = r;
  28.         rout[ans-1][1] = c;
  29.  
  30.         for(i = 0; i<4; i++)
  31.         {
  32.             int newr = r+dx[i];
  33.             int newc = c+dy[i];
  34.  
  35.             if(newr<0 || newr>m-1 || newc<0 || newc>n-1 )
  36.                 continue;
  37.  
  38.             if(visited[newr*n+newc])
  39.                 continue;
  40.  
  41.             visited[newr*n+newc] = true;
  42.             ans++;
  43.             fun(newr,newc);
  44.         }
  45.         if(i == 4) str[r*n+c] = 1;
  46.         ans--;
  47.     }
  48. }
  49.  
  50.  
  51. int main()
  52. {
  53.  
  54.     cin>>m>>n;
  55.     str = new int[m*n];
  56.     visited = new bool[m*n]();
  57.  
  58.     for(int i=0; i<m; i++)
  59.         for(int j=0; j<n; j++)
  60.         {
  61.             cin>>str[i*n+j];
  62.         }
  63.  
  64.     for(int i = 0; i<ans; i++)
  65.     {
  66.         printf("-->(%d,%d)",rout[i][0],rout[i][1]);
  67.     }
  68.     return 0;
  69. }

9.字母山谷

问题描述

　　给定一个字母矩阵，如果矩阵中的某个位置不在四条边上，而且该位置上的字母小于其上下左右四个位置的字母，则称为一个山谷。
　　例如，对于如下矩阵
　　DDDDD
　　CADCE
　　FFFFA
　　共有两个山谷，位于第二行第二列和第四列。请注意第二行第三列和第三行第五列都不是山谷。
　　对于如下30行60列的字母矩阵（请用等宽字体查看），请问有多少个山谷？　

  1. PHQGHUMEAYLNLFDXFIRCVSCXGGBWKFNQDUXWFNFOZVSRTKJPREPGGXRPNRVY
  2. STMWCYSYYCQPEVIKEFFMZNIMKKASVWSRENZKYCXFXTLSGYPSFADPOOEFXZBC
  3. OEJUVPVABOYGPOEYLFPBNPLJVRVIPYAMYEHWQNQRQPMXUJJLOOVAOWUXWHMS
  4. NCBXCOKSFZKVATXDKNLYJYHFIXJSWNKKUFNUXXZRZBMNMGQOOKETLYHNKOAU
  5. GZQRCDDIUTEIOJWAYYZPVSCMPSAJLFVGUBFAAOVLZYLNTRKDCPWSRTESJWHD
  6. IZCOBZCNFWLQIJTVDWVXHRCBLDVGYLWGBUSBMBORXTLHCSMPXOHGMGNKEUFD
  7. XOTOGBGXPEYANFETCUKEPZSHKLJUGGGEKJDQZJENPEVQGXIEPJSRDZJAZUJL
  8. LCHHBFQMKIMWZOBIWYBXDUUNFSKSRSRTEKMQDCYZJEEUHMSRQCOZIJIPFION
  9. EEDDPSZRNAVYMMTATBDZQSOEMUVNPPPSUACBAZUXMHECTHLEGRPUNKDMBPPW
  10. EQTGJOPARMOWZDQYOXYTJBBHAWDYDCPRJBXPHOOHPKWQYUHRQZHNBNFUVQNQ
  11. QLRZJPXIOGVLIEXDZUZOSRKRUSVOJBRZMWZPOWKJILEFRAAMDIGPNPUUHGXP
  12. QNJWJMWAXXMNSNHHLQQRZUDLTFZOTCJTNZXUGLSDSMZCNOCKVFAJFRMXOTHO
  13. WKBJZWUCWLJFRIMPMYHCHZRIWKBARXBGFCBCEYHJUGIXWTBVTREHBBCPXIFB
  14. XVFBCGKCFQCKCOTZGKUBMJRMBSZTSSHFROEFWSJRXJHGUZYUPZWWEIQURPIX
  15. IQFLDUUVEOOWQCUDHNEFNJHAIMUCZFSKUIDUBURISWTBRECUYKABFCVKDZEZ
  16. TOIDUKUHJZEFCZZZBFKQDPQZIKFOBUCDHTHXDJGKJELRLPAXAMCEROSWITDP
  17. TPCCLIFKELJYTIHRCQAYBNEFXNXVGZEDYYHNGYCDRUDMPHMECKOTRWOSPOFG
  18. HFOZQVLQFXWWKMFXDYYGMDCASZSGOVSODKJGHCWMBMXRMHUYFYQGAJQKCKLZ
  19. NAYXQKQOYZWMYUBZAZCPKHKTKYDZIVCUYPURFMBISGEKYRGZVXDHPOAMVAFY
  20. RARXSVKHTQDIHERSIGBHZJZUJXMMYSPNARAEWKEGJCCVHHRJVBJTSQDJOOTG
  21. PKNFPFYCGFIEOWQRWWWPZSQMETOGEPSPXNVJIUPALYYNMKMNUVKLHSECDWRA
  22. CGFMZKGIPDFODKJMJQWIQPUOQHIMVFVUZWYVIJGFULLKJDUHSJAFBTLKMFQR
  23. MYJFJNHHSSQCTYDTEAMDCJBPRHTNEGYIWXGCJWLGRSMEAEARWTVJSJBAOIOJ
  24. LWHYPNVRUIHOSWKIFYGTYDHACWYHSGEWZMTGONZLTJHGAUHNIHREQGJFWKJS
  25. MTPJHAEFQZAAULDRCHJCCDYRFVVRIVUYEEGFIVDRCYGURQDREDAKUBNFGUPR
  26. OQYLOBCWQXKZMAUSJGMHCMHGDNMPHNQKAMHURKTRFFACLVGRZKKLDACLLTEO
  27. JOMONXRQYJZGINRNNZWACXXAEDRWUDXZRFUSEWJTBOXVYNFHKSTCENAUMNDD
  28. XFDMVZCAUTDCCKXAAYDZSXTTOBBGQNGVVPJGOJOGLMKXGBFCPYPCKQCHBDDZ
  29. WRXBZMQRLXVOBTWHXGINFGFRCCLMZNMJUGWWBSQFCIHUBSJOLLMSQSGHMCPH
  30. ELSOTFLBGSFNPCUZSRUPCHYNVZHCPQUGRIWNIQXDFJPWPXFBLKPNPEELFJMT

解答：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     char str[30][60];
  8.     for(int i=0; i<30; i++)
  9.         for(int j=0; j<60; j++)
  10.             cin>>str[i][j];
  11.  
  12.     int cnt = 0;
  13.  
  14.     for(int i=1; i<29; i++)
  15.         for(int j=1; j<59; j++)
  16.         {
  17.             if(str[i][j]<str[i+1][j] && str[i][j]<str[i-1][j]
  18.                && str[i][j]<str[i][j-1] && str[i][j]<str[i][j+1])
  19.                     cnt++;
  20.         }
  21.  
  22.     cout<<cnt;
  23.     return 0;
  24. }
  25. //Answer: 276

9.马走日字

描述
马在中国象棋以日字形规则移动。

请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入
第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。

(0<=x<=n-1,0<=y<=m-1, m < 100, n < 100)
输出
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0表示无法遍历
样例输入
1
5 4 0 0
样例输出
32

tips：

A.对于这种棋盘、地图之类的问题，一定要分清楚行和列分别对应了什么

行是第一个【】，列是第二个【】，【i】【j】代表第 i 行第 j 列

如果以【0】【0】为xOy平面坐标系的原点，那么【i】【j】则表示（ i ，j ）

而输入的 n 与 m （得到了n*m的棋盘），则分别代表有n行有m列

！！！这里必须看题目给的范围：x要小于n，而y要小于m

说明横坐标的边界是n，也就是n代表列数，相应的m代表了行数！！！

所以数组输入时是arr【m】【n】，在判断nx与ny的时候也要注意分清楚边界是m还是n

是m-1还是m（每次都是边界搞好久呜呜呜）

最好是用1行2列debug一下哈哈

B.判断是否需要回溯需要看是求方案数还是求能否到达终点

求方案数需要回溯，其余的都不需要

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int m,n;
  6. int x,y;
  7. int dx[8] = { 1, 1, -1, -1, 2, -2, 2, -2};
  8. int dy[8] = { 2, -2, 2, -2, 1, 1, -1, -1};
  9. bool visited[100][100] = {false};
  10. int ans;
  11.  
  12. void dfs(int x,int y,int step)
  13. {
  14.     visited[x][y] = true;
  15.  
  16.     if(step == m*n)
  17.         ans++;
  18.  
  19.     else
  20.     {
  21.         for(int i=0; i<8; i++)
  22.         {
  23.             int nx = x+dx[i];
  24.             int ny = y+dy[i];
  25.  
  26.             if(nx<0 || nx>n-1 || ny<0 || ny>m-1)
  27.                 continue;
  28.             if(visited[nx][ny])
  29.                 continue;
  30.  
  31.             visited[nx][ny] = true;
  32.             dfs(nx,ny,step+1);
  33.             visited[nx][ny] = false;
  34.         }
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40.     int t;
  41.     cin>>t;
  42.     while(t--)
  43.     {
  44.         fill(visited[0],visited[0]+10000,false);
  45.         ans = 0;
  46.  
  47.         cin>>n>>m>>x>>y;
  48.  
  49.         dfs(x,y,1);
  50.  
  51.         cout<<ans<<endl;
  52.     }
  53.     return 0;
  54. }

变式：马怎么走才能走遍每个单元格？（只用求出一次即可，但是要打印出路径）

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int m,n;
  6. int x,y;
  7. int dx[8] = { 1, 1, -1, -1, 2, -2, 2, -2};
  8. int dy[8] = { 2, -2, 2, -2, 1, 1, -1, -1};
  9. bool visited[100][100] = {false};
  10. int ans;
  11. int foot[10001][2];
  12.  
  13. void Print(int arr[10000][2],int step)
  14. {
  15.     for(int i=1;i<step;i++)
  16.         cout<<"第"<<i<<"步:( "<<arr[i-1][0]<<" , "<<arr[i-1][1]<<" )-->"<<"( "<<arr[i][0]<<" , "<<arr[i][1]<<" )"<<endl;
  17.     cout<<"-----------------------------------"<<endl;
  18. }
  19.  
  20. void dfs(int x,int y,int step)
  21. {
  22.     visited[x][y] = true;
  23.  
  24.     if(step == m*n)
  25.         {
  26.             ans++;
  27.             Print(foot,step);
  28.         }
  29.  
  30.     else
  31.     {
  32.         for(int i=0; i<8; i++)
  33.         {
  34.             int nx = x+dx[i];
  35.             int ny = y+dy[i];
  36.  
  37.             if(nx<0 || nx>=n || ny<0 || ny>=m)
  38.                 continue;
  39.             if(visited[nx][ny])
  40.                 continue;
  41.  
  42.             visited[nx][ny] = true;
  43.             foot[step][0] = nx;
  44.             foot[step][1] = ny;
  45.             dfs(nx,ny,step+1);
  46.             visited[nx][ny] = false;
  47.         }
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     int t;
  54.     cin>>t;
  55.     while(t--)
  56.     {
  57.         fill(visited[0],visited[0]+10000,false);
  58.         ans = 0;
  59.  
  60.         cin>>n>>m>>x>>y;
  61.  
  62.         foot[0][0] = x;
  63.         foot[0][1] = y;
  64.  
  65.         dfs(x,y,1);
  66.  
  67.         cout<<ans<<endl;
  68.     }
  69.     return 0;
  70. }

另外一种表示走法：打印出的地图中每个单元格代表第 i 步

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int m,n;
  6. int x,y;
  7. int dx[8] = { 1, 1, -1, -1, 2, -2, 2, -2};
  8. int dy[8] = { 2, -2, 2, -2, 1, 1, -1, -1};
  9. bool visited[100][100] = {false};
  10. int ans;
  11. int s[100][100];
  12.  
  13. void Print(int s[100][100],int step)
  14. {
  15.     for(int i=0; i<n; i++)
  16.     {
  17.         for(int k=0; k<m; k++)
  18.             cout<<"-----";
  19.         cout<<endl;
  20.  
  21.         for(int j=0; j<m; j++)
  22.             printf("|%-3d ",s[i][j]);
  23.  
  24.         cout<<"|"<<endl;
  25.  
  26.  
  27.     }
  28.     for(int k=0; k<m; k++)
  29.         cout<<"-----";
  30.     cout<<endl;
  31.  
  32.     cout<<endl;
  33. }
  34.  
  35. void dfs(int x,int y,int step)
  36. {
  37.     visited[x][y] = true;
  38.  
  39.     if(step == m*n)
  40.     {
  41.         ans++;
  42.         Print(s,step);
  43.     }
  44.  
  45.     else
  46.     {
  47.         for(int i=0; i<8; i++)
  48.         {
  49.             int nx = x+dx[i];
  50.             int ny = y+dy[i];
  51.  
  52.             if(nx<0 || nx>=n || ny<0 || ny>=m)
  53.                 continue;
  54.             if(visited[nx][ny])
  55.                 continue;
  56.  
  57.             visited[nx][ny] = true;
  58.             s[nx][ny] = step;
  59.             dfs(nx,ny,step+1);
  60.             visited[nx][ny] = false;
  61.         }
  62.     }
  63. }
  64.  
  65. int main()
  66. {
  67.     int t;
  68.     cin>>t;
  69.     while(t--)
  70.     {
  71.         fill(visited[0],visited[0]+10000,false);
  72.         ans = 0;
  73.  
  74.         cin>>n>>m>>x>>y;
  75.  
  76.         s[x][y] = 0;
  77.  
  78.         dfs(x,y,1);
  79.  
  80.         cout<<ans<<endl;
  81.     }
  82.     return 0;
  83. }

tips：
真的搞不清x，y，m，n了呜呜呜

10.八皇后问题

问题描述

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
在这里插入图片描述
假设上图中红点为一个皇后的位置，那么他的同行，列，斜线上都不能再放置其他皇后(也就是红线覆盖的位置)

输出所有的情况（同时也考察了如何打印棋盘）

tips：

1.只需要考虑每行放一个，然后第 i 个放置的皇后的列数必须不被攻击

2.不被攻击的条件：与之前的没有在一列上&&没有在一行上（不用考虑了）&&没有在对角线上

 其中对角线的判定又包含了：主对角线和副对角线

这里可以运用函数斜率的思想（x1-x2）/ (y1-y2) = 1 那么就表示在副对角线上

同理（x1-x2）/ （y1-y2）= -1 就表示在主对角线上

这两个可以统一成abs（x1-x2）= y2 - y1（这里是因为y2肯定会大于y1，从小到大放置棋子啦）

还可以有各种各样的线（只用横纵坐标之差的比值满足特定关系即可）

  1. #include <iostream>
  2. #include <conio.h>
  3.  
  4. using namespace std;
  5.  
  6. int cnt;
  7. int pos[8];
  8.  
  9. void Print()
  10. {
  11.     int flag = 1;
  12.     cout<<"第"<<++cnt<<"种方案："<<endl;
  13.  
  14.     cout<<" ";
  15.     for(int i=0; i<8; i++)
  16.         cout<<"—";
  17.     cout<<endl;
  18.  
  19.     for(int i=0; i<8; i++)
  20.     {
  21.         cout<<"|";
  22.         for(int j=0; j<8; j++)
  23.         {
  24.             if(pos[i]==j)   
  25.                 cout<<"※";
  26.             else if(flag==1)
  27.                 cout<<"  ";
  28.             else
  29.                 cout<<"■";
  30.             flag *= -1;
  31.         }
  32.         cout<<"|"<<endl;
  33.     flag *= -1;
  34.     }
  35.  
  36.     cout<<" ";
  37.     for(int i=0; i<8; i++)
  38.         cout<<"—";
  39.  
  40.     cout<<endl;
  41.     cout<<endl;
  42.   //  getch();
  43. }
  44.  
  45.  
  46. void EightQueen(int n)//表示第n+1个棋子的放置
  47. {
  48.     if(n==8)//???
  49.     {
  50.         Print();
  51.         return;
  52.     }
  53.  
  54.     for(int i=0; i<8; i++)
  55.     {
  56.         bool flag = false;//表示尚未冲突
  57.  
  58.         pos[n] = i;//每一列都试试看行不行
  59.  
  60.         for(int j=0; j<n; j++) //判断与前面已经放置的n个棋子是否冲突
  61.         {
  62.             if(pos[j] == pos[n])
  63.                 flag = true;
  64.             else if(abs(pos[j]-pos[n]) == n-j)
  65.                 flag =true;
  66.         }
  67.  
  68.         if(!flag)
  69.             EightQueen(n+1);
  70.     }
  71. }
  72.  
  73.  
  74. int main()
  75. {
  76.     EightQueen(0);//???为什么是从0开始
  77.     return 0;
  78. }

留下来的一堆问题：

1.首先有八行八列，每次都是先确定了行数，在选取可以放置的列数

2.EightQueen（0）传入0是为了适应pos【8】下标从0开始

3.然后边界条件是n==8而不是n==7，是因为n==8时不用进行操作了，直接退出

4.pos【n】= i （i从0到7也是为了满足对列的适应），后续打印棋盘时的pos【i】 == j 也是为此

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/786980
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号