Разобраться в задаче с Codeforce - C++ - Ответ 3369291

@PG94 · Регистрация: 15.01.2012

Author24 — интернет-сервис помощи студентам

Вот условие(Задача 203B):

В один не самый прекрасный вечер Валере было очень скучно. Чтобы немного себя развлечь, Валера нашел следующее занятие.Он взял белый квадратный клетчатый лист бумаги, состоящий из n × n клеток. После этого он стал закрашивать белые клетки листа одну за другой в черный цвет. Всего он закрасил m различных клеток этого листа. Поскольку у Валеры была какая-то предрасположенность ко всему квадратному, его заинтересовал следующий вопрос — после какого хода впервые на листке можно найти черный квадрат со стороной 3. Однако Валера не знает ответ на этот вопрос и поэтому просит Вашей помощи.
От Вас требуется найти минимальный номер хода, после которого на клетчатом листке образовался хотя бы один квадрат черного цвета со стороной 3 или определить, что такого хода нет.
Входные данные
В первой строке задано два целых числа n и m (1 ≤ n ≤ 1000, 1 ≤ m ≤ min(n· n, 10⁵)) — размер клетчатого листа и количество ходов соответственно.
Далее в m строках задано описание ходов. В i-ой строке находятся два числа xi, yi (1 ≤ xi, yi ≤ n) — номер строки и номер столбца, в котором находится клетка, закрашиваемая на i-ом ходе.
Все числа в строках разделены единичными пробелами. Гарантируется, что все ходы различны. Ходы нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных. Столбцы клетчатого листа бумаги нумеруются, начиная с 1, слева направо. Строки клетчатого листа бумаги нумеруются, начиная с 1, сверху вниз.
Выходные данные
В единственной строке выведите ответ на задачу — минимальный номер хода, после которого на листе образуется черный квадрат со стороной 3. Если такого хода не существует, выведите -1.

И вот верное решение:

C++

#include<iostream>
#include<conio.h>
using namespace std;
int n,m,x,y,a[1005][1005]={0},i,l,r;
int main()
{   cin>>n>>m;
    for(i=1;i<=m;i++)
    {   cin>>x>>y;
        for(l=x;l<x+3;l++)
        {   for(r=y;r<y+3;r++)
            {   a[l][r]++;
                if(a[l][r]==9)
                {   cout<<i;
                    getch();
                    return 0;
                }
            }
        }
    }
cout<<-1;
getch();
return 0;
}

Самому задачу решить не получилось, но и логика данного кода мне не очень понятна(т.е. почему такие действия дают верный ответ). Буду очень благодарен, если кто-нибудь пояснит приведённое решение.Точнее подход к решению, т.к. сам по себе код и действия, выполняемые программой, мне понятны.

Вернуться к обсуждению:
Разобраться в задаче с Codeforce C++

Следующий ответ

Другие темы раздела
C++ Список битых полей что это такое? Хотелось бы увидеть пример кода https://www.cyberforum.ru/ cpp-beginners/ thread639254.html	C++ Загрузчик С++ Приветствую! Никак не получется собрать загрузчик, при построении в MS Visual C++ 6.0 выдает ошибки: Deleting intermediate files and output files for project 'B0_loader - Win32 Debug'. --------------------Configuration: B0_loader - Win32 Debug-------------------- Compiling... B0_loader.cpp d:\b0_loader\b0_loader.cpp(18) : warning C4305: 'initializing' : truncation from 'const int' to...
C++ Бот на С++ https://www.cyberforum.ru/ cpp-beginners/ thread639249.html Всем привет, нужен исходник бота на С++, который ходил бы по нескольким ссылкам через определённое время. Ссылки и время должны задаваться пользователем. И бот должен зайти на сайт под своим логином и паролем. Заранее спасибо.	C++ Вывод и ввод русских слов https://www.cyberforum.ru/ cpp-beginners/ thread639213.html Мне необходимо вводить слова на русском и чтобы,в дальнейшем,я мог их сравнивать с другими словами и выполнять ещё какие-то операции.В программе я пока что разбиваю фразу на слова,разделённые пробелом и вывожу их. Когда я использовал setlocale(0,""),то введённые фразы на русском языке при выводе отображались кракозяброй,если использовал нынешний вариант,то слова выводятся на русском,но при...
Окно в borland 5.02 C++ Нужно срочно окно написанное в borland 5.02. Пожалуйста помогите.	C++ Удаление последенего символа У меня есть строковая переменная. Как мне удалить из нее самый последний символ? https://www.cyberforum.ru/ cpp-beginners/ thread639190.html
C++ Работа с текстовым файлом https://www.cyberforum.ru/ cpp-beginners/ thread639183.html Вот часть кода: void ReadFile(ifstream &fin, int Kol_Ar) { //чтение данных из файла и вывод на консоль CCust *ReadF = new CCust; for(int i = 0; i < Kol_Ar; i++) {	конвектор экселя в C++ C++ Если ли какой ниб конвектор фриварный экселевского кода в С++ ???
C++ Сортировка методом подсчета https://www.cyberforum.ru/ cpp-beginners/ thread639161.html Добрый вечер,ребята очень нужен алгоритм сортировки подсчетом.Спасибо заранее.Есть вот это Это простейший вариант алгоритма. Создать вспомогательный массив C, состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A увеличить C] на единицу. Теперь достаточно пройти по массиву C, для каждого в массив A последовательно записать число j C раз....	C++ Функции для перевода числа в различные системы счисления https://www.cyberforum.ru/ cpp-beginners/ thread639149.html Здравствуйте! Подскажите пожалуйста, есть ли в С++ встроенные функции для переовда числа из одной каой либо системы счисления в другую какую либо систему счисления(меня интересует только действия над 8ой, 2ой, 16ой, 10 ой системами счисления). Если такие есть, то перечислите пожалуйста их все. Заранее спасибо!
затрудняюсь с алгоритмом подсчета кол-ва встречаемых цифр C++ Затрудняюсь составить алгоритм подсчета количества встречаемых цифр в числе, например в 1231322221 или 3222222123 встречаются 3 цифры 1,2 и 3, результат = 3, 556333344365 {3,4,5,6}=4 и.т.п.. (буду признателен за ответ)	C++ MinGW for Windows - libpng ./configure - error: zlib not installed https://www.cyberforum.ru/ cpp-beginners/ thread639137.html Пользуюсь MinGW for Windows. Устанавливалось согласно этого мануала: http://wiki.openttd.org/Компиляция_на_MinGW/Ru (открывайте копированием в броузер а не кликом) Но версии библиотек я применял последние, а не те которые в мануале (устаревшие). Дошел до пункта: Компиляция libpng выполняю: ./configure жужжит, и потом вылазит ошибка - error: zlib not installed

	18.08.2012, 11:36