二维数组八个方向的判断--牛客刷题1023-病菌感染

2024-03-09 05:10

本文主要是介绍二维数组八个方向的判断--牛客刷题1023-病菌感染,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

铁子和顺溜上生物课的时候不小心将几滴超级病菌滴到了培养皿上,这可急坏了他们。
培养皿可以被看成一个n*n的方格,最初病菌滴在了这n*n的格子中的某些格子,病菌的传染方式是这样的,如果一个方格与两个或多个被感染的方格相邻(两个方格相邻当且仅当它们只有一条公共边),那么它就会被感染。现在铁子和顺溜想知道,最终所有的方格会不会都被感染。

输入描述:

第一行两个整数n,m。n表示方格的规格,m表示最初病菌所在的格子数。(1 ≤ n ≤ 1000, 0 < m < n)。

接下来m行每行两个整数xi,yi表示第xi行的第yi个格子有病菌。

数据保证不会有两个病菌初始时在同一个格子。

输出描述:

如果最终所有的方格都会被感染,输出 YES。
否则输出 NO。

示例1

输入

3 2
1 2
2 2

输出

NO

我们先去分析题的大意

  • 一个n*n的方格  :明显是个矩阵----> 要用到二维数组了
  • ,如果一个方格与两个或多个被感染的方格相邻(两个方格相邻当且仅当它们只有一条公共边),那么它就会被感染。现在铁子和顺溜想知道,最终所有的方格会不会都被感染
  • 这个说明的是病毒是在四个方向上进行的,上 下 左 右:
  • 接下来m行每行两个整数xi,yi表示第xi行的第yi个格子有病菌。
  • 数据保证不会有两个病菌初始时在同一个格子。 --------->是说输入坐标

其实说到这里,大致是有自己的方向来判断了,就是在上下左右四个方向上来判断呗,为了便于理解,我按照题意打印出如下图形,0(病毒),那么我就开始去走起

 这个是便于理解,但是在做题的时候,为了方便,我直接把所有的元素变成了0,那么是病毒是则是1,然后我在遍历中走一圈的时候,可以来进行加法,当大于2时,就说明你的周围是最少有三个病毒,然后就被感染,然后在遍历走去

while (m > 0) {
        cin >> x >> y;
        arr[x][y] = 1;
        m--;
    } 

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {    
            if (arr[i][j] != 1) { //上下左右四个方向的判断
                t = arr[i][j] + arr[i][j + 1] + arr[i][j - 1] + arr[i + 1][j] + arr[i - 1][j];
                if (t < 2){cout << "NO" << endl; return 0;} 
            }       

        }

    }
    cout<<"YES"<<endl;
return 0;

 全部的代码如下

#include <iostream>
#include <iomanip>
#define N 1001
using namespace std;
int main()
{int arr[N][N] = {0};int n, m, i, j, x, y,t, flag = 0;cin >> n >> m;while (m > 0) {cin >> x >> y;arr[x][y] = 1;m--;} for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){if (arr[i][j] != 1) { //上下左右四个方向的判断t = arr[i][j] + arr[i][j + 1] + arr[i][j - 1] + arr[i + 1][j] + arr[i - 1][j];if (t < 2){cout << "NO" << endl; return 0;} }}}cout<<"YES"<<endl;
return 0;return 0;
}

经过这个想一下如果八个方向呢?

我开始的时候是思考的是八个方向,最开始的时候想的没有那么完善,是这样的

num = 0;
                if (0 != arr[i][j + 1]) num++;// 右
                if (0 != arr[i][j - 1]) num++;//左
                if (0 != arr[i+1][j]) num++;//下
                if (0 != arr[i-1][j]) num++;//上
                if (0 != arr[i+1][j + 1]) num++; //右下
                if (0 != arr[i+1][j-1]) num++;//左下
                if (0 != arr[i-1][j + 1]) num++; //左下
                if (0 != arr[i-1][j - 1]) num++;//左上
                //if (num > 6&&arr[i][j]!=0) cout << arr[i][j]<<endl;
                if (num > 6 && arr[i][j] != 0) flag = 1;

我对八个方向来分析,如果说 他们在这个方向上有不是0的那就说明没有病毒,当没有病毒是的个数大于六时候说明就不能被感染,然后我前边还设置一个flag呢,只要有一个不被感染那就说明不被感染,那就当然是 NO 下面的这个不完整哈,只是一个想法而已,仅供参考

#include <iostream>
#include <iomanip>
#define N 101
using namespace std;
int main()
{int arr[N][N];int n,m,i,j,t=1,x,y,num,flag=0;cin >> n>>m; for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){arr[i][j]=t++;}}while (m > 0) {cin >> x >> y;arr[x][y] = 0;m--;}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){num = 0;if (0 != arr[i][j + 1]) num++;// 右if (0 != arr[i][j - 1]) num++;//左if (0 != arr[i+1][j]) num++;//下if (0 != arr[i-1][j]) num++;//上if (0 != arr[i+1][j + 1]) num++; //右下if (0 != arr[i+1][j-1]) num++;//左下if (0 != arr[i-1][j + 1]) num++; //左下if (0 != arr[i-1][j - 1]) num++;//左上//if (num > 6&&arr[i][j]!=0) cout << arr[i][j]<<endl;if (num > 6 && arr[i][j] != 0) flag = 1;}}if (flag == 1) cout << "YES"<<endl;else cout << "NO" << endl;for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){cout<< arr[i][j]<<setw(4);}cout <<"\n";}return 0;
}
1

这篇关于二维数组八个方向的判断--牛客刷题1023-病菌感染的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/789611

相关文章

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

CSS3 最强二维布局系统之Grid 网格布局

《CSS3最强二维布局系统之Grid网格布局》CS3的Grid网格布局是目前最强的二维布局系统,可以同时对列和行进行处理,将网页划分成一个个网格,可以任意组合不同的网格,做出各种各样的布局,本文介... 深入学习 css3 目前最强大的布局系统 Grid 网格布局Grid 网格布局的基本认识Grid 网

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu