Формат выходных данных

Выведите «YES», если граф является полным, и «NO» в противном случае.

Примеры

Входные данные	Выходные данные
3 3 1 2 1 3 2 3	YES
3 2 1 2 2 3	NO

Задача №244.  Цветной дождь

В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами. В некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Посчитайте количество таких "плохих" мостов.

Входные данные

В файле INPUT.TXT в первой строке записано N (0 < N ≤ 100) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). Предпоследняя строка пустая, а в последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.

Выходные данные

В файл OUTPUT.TXT вывести количество "плохих" мостов.

Пример

INPUT.TXT	OUTPUT.TXT
7 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0   1 1 1 1 1 3 3	4

Решение

#include <fstream>

#define SIZE 101

using namespace std;

main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

int link[SIZE][SIZE], color[SIZE], n, i, j, ans = 0;

cin >> n;

for(i = 0; i < n; i++)

   for(j = 0; j < n; j++)

       cin >> link[i][j];

for(i=0; i<n; i++)

   cin >> color[i];

for(i = 0; i < n-1; i++)

   for(j = i+1; j < n; j++)

       if(link[i][j]  &&  color[i] != color[j]) ans++;

cout << ans;

}

Задача №245.  Граф-турнир (e-olymp)

Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одна дуга.

Для заданного списком дуг графа проверьте, является ли он турниром.

Входные данные

Входной файл содержит числа N (1 ≤ N≤100) - число вершин в графе и M (1≤M≤N×(N - 1)) - число дуг. Затем следует M пар чисел - дуги графа.

Выходные данные

Выведите в выходной файл YES, если граф является турниром и NO в противном случае.

Пример

Ввод	Вывод
3 3 1 2 1 3 3 2	YES
3 4 1 2 2 1 2 3 1 3	NO

Решение

Очевидно, граф не может являться турниром, если между двумя его вершинами дуг нет вообще или их две.

#include <iostream>

int A[100][100];

int main() {

int n, m, a, b;

std::cin >> n >> m;

for (int i = 0; i < m; i++) {

std::cin >> a >> b;

A[--a][--b]=1;

}

for (int i = 0; i<n; i++)

for (int j = i+1; j<n; j++)

       if (A[i][j] == A[j][i]) {

           std::cout << "NO\n";

           return 0;

       }

std::cout << "YES\n";

}

Задача №246.  Камень, ножницы, бумага и другие

Автор: Г. Гренкин

Ограничение времени на тест:    1 сек

Ограничение памяти на тест:      256 Мб

Глеб и Вася, студенты Института математики и компьютерных наук ДВФУ, часто играют в игру "камень, ножницы, бумага", чтобы определить, кто пойдёт мыть тряпку для стирания с доски.

Однажды Глеб и Вася захотели обобщить игру "камень, ножницы, бумага". Теперь в игре задействовано N предметов. Задаётся список пар предметов. Считается, что если один игрок выбрал первый предмет из некоторой пары, а другой игрок — второй предмет из этой пары, то тот, кто выбрал первый предмет из пары, побеждает. Если игроки выбрали пару предметов, которая не встречается в списке пар, то объявляется ничья.

Напишите программу, принимающую на вход выбранные игроками предметы и выводящую результаты игры. Своё решение можете протестировать с помощью схемы:

Решение

Очевидно, результаты всех игр можно задать с помощью матрицы смежности, в которой Aij принимает значение 1 если предмет i побеждает предмет j. На схеме в самой игре используется нечетное число предметов N = 2K + 1, т.е. K предметов побеждают выбранный и K ему проигрывют. Это позволит не задавать матрицу смежности вручную, а заполнить её с помощью цикла (каждый предмет побеждает N/2 предыдущих). Для перехода от названий предметов к их номерам можно воспользоваться ассоциативным массивом map.

#include <iostream>

#include <map>

#define N 15

using namespace std;

int main() {

string name[N] = {"Gun", "Lightning", "Devil", "Dragon", "Water",

                 "Air", "Paper", "Sponge", "Wolf", "Tree",

                 "Human", "Snake", "Scissors", "Fire", "Rock"},

       s1, s2;

map<string, int> v;

for(int i = 0; i < N; i++)

   v[name[i]] = i;

   

int a[N][N] = {0,}, d;

for(int i = 0; i < N; i++)

   for(int j = 1; j <= N/2; j++)

       a[i][N*(j>i)+ i - j] = 1;

   

cin >> s1 >> s2;

d = a[v[s1]] - a[v[s2]];

cout << (!d ? "DRAW" : (d > 0 ? "WIN" : "LOSE"));

}

Поиск в глубину

Идея метода. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:

       Nnew : array[1..N] of boolean. 

Задача №247.  Острова(Симферополь, IIэтап, 2014)

Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.

Примечание: одна единица тоже считается островом.

Входные данные

В первой строке файла iseland. in записано натуральное число N не больше 100 - размер квадратной матрицы. В следующих N строках задаются элементы матрицы через пробел.

Выходные данные

В файл iseland. out выведите единственное число - количество островов.

Пример

iceland.in	iceland.out
5 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1	4

Решение

#include <iostream>

 

Задача №248.  Железная дорога (Симферополь, IIэтап, 2015)

Вася Пупкин играет в компьютерную игру Transport Tycoon Deluxe, где ему очень нравится быть транспортным магнатом, владеющим сетью железных дорог, соединяющей различные города на карте между собой. Помогите Васе определить, в сколько городов можно попасть из некоторого города, используя его железную дорогу.

Входные данные

В первой строке заданы два числа Nи K–общее количество городов и номер города, для которого выполняется подсчет (1 <= N <= 100; 1 <= K<= N). В следующих Nстроках – матрица из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что между городами с номерами i и j Вася строил дорогу, а 0 – не строил.

Выходные данные

Одно число – количество городов, в которые можно попасть из данного города K.

Пример

Ввод	Вывод
5  1	3
0  0  1  0  0
0  0  1  0  0
1  1  0  0  0
0  0  0  0  1
0  0  0  1  0

Примечание: Из города 1 можно попасть в город 1, естественно, город 3 и город 2 (через 3)

Решение

Данная задача рационально решается с применением алгоритма обхода графа в глубину. Заведем массив b, который будет определять, можно ли попасть в указанный город. При описании рекурсивной процедуры dfs будем вызывать её только для тех городов, в которых мы еще не побывали. Это убережет нас от «вечной рекурсии».

#include <iostream>

#define SIZE 100

int n, k, cnt=0;

bool a[SIZE][SIZE], used[SIZE];

 

void dfs(int node){  //обход в глубину

used[node] = true;    //запоминаем вершину как пройденную

cnt++;                //увеличиваем счетчик посещений

for (int i = 0; i<n; i++) //проверяем все не посещенные ранее

   if (a[node][i] && !used[i])

       dfs(i);

}

int main() {

std::cin >> n >> k;

for (int i = 0; i < n; i++) //чтение матрицы смежности

   for (int j = 0; j < n; j++)

       std::cin >> a[i][j];

dfs(--k);

std::cout << cnt;

}

Скачки (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Иван Иванович любит ходить на скачки, надеясь на них заработать кругленькую сумму. Ему приглянулась лошадь с номером K, и он решил проверить, сможет ли она выиграть у всех остальных лошадей. Иван Иванович раздобыл информацию, в которой для некоторых пар лошадей сообщается, какая из этих лошадей быстрее. Также он узнал, что у всех лошадей разные скорости.

Требуется написать программу, которая поможет Ивану Ивановичу точно определить может ли выиграть выбранная им лошадь.

Входные данные

В первой строке два целых числа N (1 ≤ N ≤ 100) и K (1 ≤ K ≤ N), где N – количество лошадей, принимающих участие в скачках, K – номер лошади, на которую хочет сделать ставку Иван Иванович. Следующие строки содержат по два числа X и Y (1 ≤ X, Y ≤ N), обозначающие, что лошадь с номером X быстрее лошади с номером Y. Пары X и Y не повторяются. Набор данных завершается строкой, содержащей единственный ноль. Эту строку обрабатывать не надо.

Гарантируется, что информация, раздобытая Иваном Ивановичем, корректна.

Выходные данные

Вывод должен содержать слово «Yes», если Иван Иванович уверен в своем выигрыше и «No» в противном случае.

Примеры

№	Ввод	Вывод
1	3  1 1  2 1  3 0	Yes
2	3  2 2  3 0	No
3	4  2 3  1 2  3 0	No

Решение

Решим задачу построением матрицы смежности, где для двух лошадей i и j будем ставить 1, если лошадь i быстрее.

#include <iostream>

using namespace std;

int n, k, x, y, cnt;

bool a[100][100], used[100];

 

void dfs(int node){             // обход в глубину

used[node] = true;

cnt++;

for(int i = 0; i < n; i++)

   if(!used[i] && a[node][i]) dfs(i);

}

 

int main () {

cin >> n >> k;

while(true){                     // чтение данных

   cin >> x;

   if(!x) break;

   cin >> y;

   if(y == k){

       cout << "No";

       return 0;

   }

   a[--x][--y] = 1;

}

dfs(--k);

cout << (cnt == n ? "Yes" : "No");

}

Задача №249.  Вавилонская башня

При строительстве Вавилонской башни, как известно, Бог смешал все языки. В результате оказалось, что каждый человек знает некоторое множество языков (не более 100). Два человека могут передать друг другу информацию, если существует язык, который они оба знают. Руководитель стройки передает команды на известных ему языках. Те, кто эти команды получил, могут их передавать дальше, переводя на известные им языки. Определить количество людей, до которых доходят команды руководителя.

Входные данные

В первой строке задано количество людей N (1≤N≤500), а дальше идут описания того, какие языки знают эти люди. Для каждого человека записано сначала число M_i (0≤M_i≤100), определяющее количество языков, известных i-ому человеку, а затем перечисляются номера самих этих языков в возрастающем порядке. Каждый номер – натуральное число от 1 до 100000. Считается, что руководитель строительства — это человек с номером 1.

Выходные данные

Вывести одно число — количество человек, до которых может «дойти» отданная руководителем команда (включая самого руководителя).

Примеры

Ввод	Вывод
5 2 1 2 1 1 2 2 3 0 2 4 5	3
8 3 1 4 8 3 2 4 15 3 12 14 19 2 14 33 2 8 11 4 2 4 18 21 1 15 2 21 23	6

Решение

Эта тожезадача на графы, которая решается методом обхода в глубину. Единственная «изюминка» задачи состоит в заполнении матрицы смежности. Применим в решении две вспомогательные функции – dfs (для обхода графа в глубину) и link(для проверки, может ли строитель p₁общаться со строителем p₂).

Для ускорения работы второй функции используем факт того, что номера языков, известных строителю, упорядочены по возрастанию.

#include <iostream>

#define LANGS 100

#define MANS 500

int lang[MANS][LANGS+1],n,cnt;

bool man[MANS][MANS],used[MANS];

 

void dfs(int node){             //обход в глубину

used[node]=true;

cnt++;

for(int i=0;i<n;i++)

   if(man[node][i] && !used[i])dfs(i);

}

bool link(intp1,intp2){   //проверкаобщихязыков 2 строителей

int k1=1,k2=1;

while(k1<=lang[p1][0]&&k2<=lang[p2][0]){

   if(lang[p1][k1]==lang[p2][k2])return true;

   else{

       if(lang[p1][k1]>lang[p2][k2])k2++;

       else k1++;

   }

}

return false;

}

int main(int argc, char** argv) {

std::cin>>n;

for(int i=0;i<n;i++){

std::cin >> lang[i][0];     //чтение массива языков

for(int j = 1; j <= lang[i][0]; j++)

    std::cin>>lang[i][j];

   for(intj=i;j>=0;j--){ //заполнение матрицы смежности

man[i][j]=link(i,j);

       man[j][i]=man[i][j];

   }

}

dfs(0);

std::cout<<cnt<<"\n";

}

Рассмотрим задачу, где требуется подсчитать компоненты связности – подграфы, в каждом из которых между двумя любыми вершинами существует путь.

Задача №250.  Заповедники(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

В райской долине расположено N заповедников, имеющих форму прямоугольников. Однажды на собрании директоров было принято решение об увеличении площадей заповедников. Для этого директор каждого заповедника выбрал Ri - количество метров, на которое он хочет увеличить зону своего заповедника, смотрите рисунок. Однако после подписания соглашения выяснилось, что некоторые заповедники имеют общие земли. Такие заповедники было решено объединить в один, если объединенный заповедник пересекался с еще каким-нибудь заповедником их опять объединяли и так до тех пор пока не остались заповедник(и) не имеющие общих земель.

Ваша задача посчитать, сколько заповедников стало в долине после объединения.

Входные данные

Первая строка содержит число N (1 ≤ N ≤ 100) – количество заповедников. Далее идет N строк содержащих по пять целых чисел x₁, y₁, x₂, y₂, R. (x₁, y₁) и (x₂, y₂) – координаты противоположных вершин заповедника в метрах (-10⁴ ≤ x₁, y₁, x₂, y₂ ≤ 10⁴ ).

Стороны заповедников параллельны осям координат. Заповедники, имеющие общую границу, считаются пересекающимися. R (0 ≤ R ≤ 10⁴) – расстояние, на которое отодвигается граница заповедника.

Выходные данные

Выведите одно натуральное число – количество оставшихся заповедников после объединения.

Пример

Ввод	Вывод
3 3 1 6 4 1 1 -2 2 -3 1 -2 -2 -1 -3 2	2

Решение

#include <iostream>

#define SIZE 100

#define IN(a,b,c) (b<=a && a<=c)     //проверкапринадлежности отрезку

using namespace std;

int a[SIZE][SIZE], used[SIZE], x1[SIZE], y1[SIZE],

   x2[SIZE], y2[SIZE],

   n, r, i, j;

void dfs(int node) {      // обходграфавглубину

used[node] = true;

for (int next = 0; next < n; next++)

     if (a[node][next] && !used[next]) dfs(next);

}

 

int main(){

cin >> n;

for(i = 0; i < n; i++){

   cin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> r;

   if(x1[i] > x2[i]) swap(x1[i], x2[i]); //упорядочение

   if(y1[i] > y2[i]) swap(y1[i], y2[i]); //вершинзаповедника

   x1[i] -= r; y1[i] -= r; // расширение заповедника

x2[i] += r; y2[i] += r;

   for(j = 0; j<i; j++){   // проверка пересечений

r = (IN(x1[j], x1[i], x2[i]) || IN(x2[j], x1[i], x2[i])) &&

          (IN(y1[j], y1[i], y2[i]) || IN(y2[j], y1[i], y2[i])) ||

          (IN(x1[i], x1[j], x2[j]) || IN(x2[i], x1[j], x2[j])) &&

          (IN(y1[i], y1[j], y2[j]) || IN(y2[i], y1[j], y2[j]));

      a[i][j] = r;         // заполнение матрицы смежности

a[j][i] = r;

   }

}

 

for (r = i = 0; i<n; i++)   // подсчет компонент связности

if (!used[i]) {

       dfs(i);

       ++r;

   }

cout << r;

}

Задача №251.  Горные маршруты

Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?

Входные данные

В первой строке через пробел записаны числа n, k, a, b, d (n ≤ 50, d ≤ 10). Каждая из следующих k строк содержит пару чисел, которая описывает возможный горный переход. Все числовые значения натуральные.

Выходные данные

Вывести одно число - количество маршрутов.

Пример

Ввод	Вывод	Граф (пояснение к задаче)
5 8 2 5 3 1 2 1 3 1 5 2 1 2 4 3 4 3 5 4 1	3

Решение

В данной задаче нам требуется при перемещении в очередную точку пути учитывать, сколько при этом прошло дней

#include <iostream>

#define SIZE 51

using namespace std;

bool used[SIZE]={0,},link[SIZE][SIZE]={0,};

int n, k, a, b, d, cnt = 0, days = -1;

void dfs(int base){

if(base == b){              //нашли еще 1 маршрут

   cnt++;

   return;

}

days++;

used[base] = true;          //помечаем вершину как пройденную

for(int i = 1; i <= n; i++) //перебираем связанные с ней

   if(link[base][i] && !used[i] && days<d) dfs(i);

days--;

used[base] = false;

}

int main() {

cin >> n >> k >> a >> b >> d;

int t1, t2;

for(int i = 0; i<k; i++){

   cin >> t1 >> t2;

   link[t1][t2] = 1;

}

dfs(a);

cout << cnt;

}

Поиск в ширину

Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”.

 

Задача «Проверка схем»

Представить схему с помощью графа. Определить наилучшие тесты

задача «ходы шахматного коня»

Задача №252.  Шахматный конь

Имеется шахматная доска размером N×N. Часть клеток вырезана, и на них ходить нельзя. Шахматный конь находится в позиции X1, Y1(левый верхний угол имеет координаты 1,1). Требуется определить, за какое наименьшее число ходов он сможет добраться до клетки X2,Y2. Если дойти невозможно, вывести -1.

Входные данные

В первой строке файла “horse.in” через пробел 5 чисел 0<N≤100. Затем  0≤X1,Y1,X2,Y2≤N

В последующих Nстроках содержится ровно по Nчисел, где 1 означает целую клетку, а 0 –вырезанную.

Выходные данные

В файле “horse.out” одно число – минимальное количество ходов, за которое шахматный конь может добраться из X1,Y1 до X2,Y2. Если дойти невозможно, вывести -1.

Пример

horse.in	horse.out
7 2 3 3 4 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	2
7 2 3  7 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	-1

Решение

Идея решения достаточно проста – поставим в первую клетку, куда можно попасть конем, значение 1. Во все клетки, в которые можно попасть из клетки со значением 1 за один ход, поставим значение 2. В тех клетках, куда можно попасть за 1 ход из клетки со значением 2, установим значение 3 и т.д.

Нам потребуется для решения задачи структура данных «очередь». Воспользуемся заголовочным файлом queue, описывающем очередь в STL.

При чтении матрицы, описывающей шахматную доску, уменьшим каждое значение на 1. В дальнейшем при проверке возможных ходов коня будем искать только те клетки, у которых значение 0.

Вначале проверим, не находится ли конь на вырезанной клетке, и не нужно ли ему прийти в вырезанную клетку. Отбросив эти варианты, принимаем значение первой клетки, куда ставится конь, за единицу. Её координаты записываем в очередь.

Далее, будем обрабатывать очередь, пока она не опустеет, следующим образом: считываем из очереди xи y. Затем проверяем все клетки, куда можно попасть из x,yза 1 ход коня. Ставим эти клетки в конец очереди, а значение в этой ячейке матрицы поля берём на единицу больше, чем было в x,y. Таким образом, матрица поля для обоих примеров к моменту окончания работы с очередью будет выглядеть так.

2 3 2 5 4 3 0 3 4 3 2 -1 4 5 4 1 4 3 4 -1 4 3 4 3 2 3 4 5 2 3 2 5 4 3 4 3 4 3 4 3 4 5 4 3 4 3 4 5 4

В каждой невырезанной клетке число, на единицу большее минимального количества ходов коня для достижения этой клетки из X1,Y1. Листинг программы на C++, реализующей данное решение, может выглядеть следующим образом:

#include<fstream>

#include<queue>           // заголовочный файл очереди

#define SIZE 100

using namespace std;

int field[SIZE][SIZE], n,

dx[8]={-2,-2,-1,-1,1,1,2,2},//ходы шахматного коня

   dy[8]={-1,1,-2,2,-2,2,-1,1};//ходы шахматного коня

bool correct(int a,int b){     //проверкадоступностиполя

if(0<=a && a<n && 0<=b && b<n)return !field[a][b];

else return false;

}

int main(){

queue<int> chess;  // пустаяочередь chess (тип int)

int x2,y2,x,y,i,j;

ifstream cin("horse.in"); //переопределяемпотоки

  ofstream cout("horse.out");

cin>>n>>x>>y>>x2>>y2;

for(i=0;i<n;i++)

   for(j=0;j<n;j++){

       cin>>field[j][i];

       field[j][i]--;

}

if(field[x][y]||field[x2][y2]){ //есликоньстоитнавырезанной

cout<< -1;           //клеткеилидолженприйтивнеё

return 0;

}

chess.push(--x); chess.push(--y); field[x][y]=1;

while(!chess.empty()){ //ставим все доступные ходы в очередь

x=chess.front(); chess.pop();   //читаемx и извлекаем

y=chess.front(); chess.pop();   //читаемy и извлекаем

for(i=0;i<8;i++) //проверяем клетки в досягаемости 1 хода

if(correct(x+dx[i],y+dy[i])){ //клетка есть и не занята

chess.push(x+dx[i]);

           chess.push(y+dy[i]);

           field[x+dx[i]][y+dy[i]]=field[x][y]+1;

       }

  }

cout<<--field[--x2][--y2];

}

Задача №253.  Числа Эрдёша

 

Задача №254.  Табличка(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Вам дана табличка, состоящая из N строк и M столбцов. В каждой клетке таблицы стоит либо 0, либо 1. Расстоянием между клетками (x1,y1) и (x2,y2) называется |x1-x2|+|y1-y2|. Вам нужно построить другую таблицу, в которой в каждой клетке стоит расстояние от данной до ближайшей клетки, содержащей 1 (в начальной таблице). Гарантируется, что хотя бы одна 1 в таблице есть.

Входные данные

В первой строке входного файла INPUT.TXT содержатся два натуральных числа, не превосходящих 100 - N и M. Далее идут N строк по M чисел - элементы таблицы.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать N строк по M чисел - элементы искомой таблицы.

Пример

INPUT.TXT	OUTPUT.TXT
2 3 0 0 1 1 0 0	1 1 0 0 1 1

Решение

При решении данной задачи удобно все введённые числа в матрице уменьшить на 1. Таким образом все единичные элементы станут нулями, что и требовалось в задаче, а еще не просчитанные станут отрицательными. Далее воспользуемся волновым алгоритмом и STL-контейнером queue (очередь), в который будем записывать координаты клеток, начиная от единиц.

#include<fstream>

#include<queue>           // очереди

using namespace std;

intn, m, a[100][100], i, j;

queue<int>q;              //создаём пустую очередь ходов

 

voidcheck(inty, intx){    //проверкаклеткитаблицы

if(0<=x && x<m && 0<=y && y<n && a[y][x]<0){

   a[y][x] = a[i][j] + 1; // если клетка существует и еще не

q.push(y);      // использовалась, то увеличиваем её

q.push(x);      // на 1 и ставим в очередь

}

}

int main(){

ifstream cin("input.txt");

ofstream cout("input.txt");

cin >> n >> m;

for(i = 0; i < n; i++)

   for(j = 0; j < m; j++){

       cin>>a[i][j];

if(a[i][j]--){  // исходные значения уменьшаем на 1

q.push(i); //координаты всех единиц записываем

q.push(j); // в очередь

       }

   }

 

while(q.size()){                // пока очередь не пуста

i = q.front(); q.pop();   // извлекаем координаты

j = q.front(); q.pop();   // следующей клетки

check(i-1, j);       // и проверяем её соседей

check(i+1, j);

   check(i, j-1);

   check(i, j+1);

}

for(i = 0; i < n; i++){     //выводрезультата

   for(j = 0; j < m; j++)

       cout << a[i][j] << ' ';

   cout << endl;

}

}

Задача №255.  Игра с фишками (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Источник задачи: Московская олимпиада по информатике 2002/2003 г.

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку. Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:

Путь должен состоять из отрезков вертикальных и горизонтальных прямых.

Путь не должен пересекать других фишек. При этом часть пути может оказаться вне доски. Например:

Фишки с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и (5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4) соединить нельзя – любой соединяющий их путь пересекает другие фишки.

Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или «мнимых клеток», расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

Рис. 47. Иллюстрация к задаче "Игра с фишками"

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа: W – ширина доски, H – высота доски (1≤W,H≤75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ «X» (заглавная английская буква «экс») обозначает фишку, символ «.» (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами – X₁, Y₁, X₂, Y₂, причём 1≤X₁,X₂≤W, 1≤Y₁,Y₂≤H. Здесь (X₁, Y₁) и (X₂, Y₂) – координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.

Выходные данные

Для каждого запроса в выходной файл OUTPUT.TXT необходимо вывести одно целое число на отдельной строке – длину кратчайшего пути, или 0, если такого пути не существует.

Пример

INPUT.TXT	OUTPUT.TXT
5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0	5 6 0

Решение

Будем обозначать занятую фишкой клетку -1, а свободную нулём.

Для решения задачи с возможностью выходить за край поля добавим по краям две пустых вертикали и две пустых горизонтали. После этого можно использовать волновой алгоритм (обход графа в ширину). Т.е. в начальной клетке пути поставим 1, в тех, куда можно попасть из неё за 1 ход 2 и т.д.

После прохождения аждого теста необходимо восстанавливать поле, т.е. все клетки, в которых значение больше 0 необходимо опять обнулить.

#include <fstream>

#include <queue>

#define PUSH(y,x) {a[y][x] = a[i][j]+1; Q.push(x); Q.push(y);}

using namespace std;

int w, h, a[78][78], i, j, x1, y1, x2, y2;

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

char c;

cin >> w >> h;

for(i = 1; i <= h; i++)

   for(j = 1; j<= w; j++){

       cin >> c;

       a[i][j] = -(c=='X');               // Xзаменяем на -1

}                                    // остальное - нули

while(true){

queue<int>Q;                         // пустая очередь

cin >> x1 >> y1 >> x2 >> y2;

   if(x1 || y1 || x2 || y2) return 0;

   a[y1][x1] = 1; a[y2][x2] = 0;     // помечаем начало и

Q.push(x1); Q.push(y1);              // конец пути

while(Q.size() && !a[y2][x2]){

       j = Q.front(); Q.pop();       //извлекаемi иj

       i = Q.front(); Q.pop();       // из очереди

       if(i && !a[i-1][j]) PUSH(i-1,j); //затем проверяем

       if(i<=h && !a[i+1][j]) PUSH(i+1,j); //соседние клетки

       if(j && !a[i][j-1]) PUSH(i,j-1);

       if(j<=w && !a[i][j+1]) PUSH(i,j+1);

   }

   cout << (a[y2][x2] ? a[y2][x2]-1 : 0) << endl;

 

   a[y1][x1] = a[y2][x2] = -1;  // восстанавливаем поле

for(i = 0; i < h+2; i++)

       for(j = 0; j < w+2; j++)

           if(a[i][j]>0)a[i][j] = 0;

}

}

В некоторых задачах с применением волнового алгоритма требуется не только найти длину кратчайшего пути, но и восстановить сам путь. Рассмотрим такую задачу.

Задача №256.  Lines – 2(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.

Входные данные

В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. (2 ≤ N ≤ 250)

Выходные данные

Выведите в первой строке «Y», если движение возможно, или «N», если нет. Если движение возможно, то далее следует вывести N строк по N символов - как и на вводе, но буква X, а также все точки по пути следует заменить плюсами. Если решений несколько, выведите любое.

Примеры

№	Ввод	Вывод
1	5 ....X .OOOO ..... OOOO. @....	Y +++++ +OOOO +++++ OOOO+ @++++
2	5 ..X.. ..... OOOOO ..... ..@..	N
3	5 ...X. ..... O.OOO ..... ....@	Y ..++. .++.. O+OOO .++++ ....@

Решение

При решении удобно использовать несколько вспомогательных функций

· put– для помещения координат клетки в очередь

· get – для извлечения первого числа из очереди

· check– проверка клетки с заданными координатами для восстановления пути от конечной точки до начальной

При чтении исходных данных помечаем недоступные клетки как -1. В начальную ставим 1, в соседние с ней 2, в соседние с ними 3 и т.д. При этом будем реализовывать волновой алгоритм с помощью очереди. Будем повторять эти действия пока очередь не опустеет или пока не удастся дойти до клетки конца пути.

Следующей нашей задачей станет восстановление пути. Будем идти от конца пути к началу. Для этого проверяем каждый раз соседние с данной клетки, в которых значение на единицу меньше, чем в текущей. Затем переходим в такую клетку, предварительно отметив текущую как -2. В последнюю клетку (начальную) поставим -3.

Осталось вывести матрицу с путём. Очевидно, что для значения -3 надо вывести символ @, для -2 символ +, для -1 символ O, а всем остальным соответствует точка.

#include<iostream>

#include<queue>

#defineSIZE 250

usingnamespacestd;

 

inta[SIZE][SIZE], n, i, j, x, y;

queue<int> q;

 

voidput(intl, intm){      // поместитькоординатывочередь

if (~l && l<n && ~m && m<n && !a[l][m]){

   a[l][m] = a[i][j] + 1;

   q.push(l); q.push(m);

}   

}

 

voidget(int&v){           // извлечь из очереди

v = q.front(); q.pop();

}

 

voidcheck(intl, intm){          // поиск следующей клеткипути

if (~l && l<n && ~m && m<n && a[l][m] == a[y][x]-1){

   i = l; j = m;

}

}

int main(){

char c;

cin >> n;  

for(i = 0; i<n; i++)        // чтениеисходныхданных

for(j = 0; j < n; j++){

       cin>>c;

if(c == 'O') a[i][j] = -1; // в недоступных ставим -1

if(c == 'X') {y = i; x = j;} // запоминаем конечную

if(c == '@') put(i, j);   // начальную - в очередь

}

while(q.size() && !a[y][x]){    // реализация bfsобхода в ширину

get(i); get(j);      // извлекаем координаты клетки

put(i-1, j);              // проверяем соседние клетки

put(i+1, j);              // если они доступны, ставим их

put(i, j-1);              // вочередь

   put(i, j+1);

}

cout << (a[y][x] ? 'Y' : 'N') << endl;

if(!a[y][x]) return 0;      // если пути нет, то выходим

while (a[y][x] > 0){      // ищем путь от последней клетки

check(y - 1, x);          // до начальной

check(y + 1, x);

check(y, x - 1);

   check(y, x + 1);

   a[y][x] = -2;                // ставим в текущую -2

y = i; x = j;             // и идём в следующую

}

a[y][x] = -3;             // ставим в первую -3

 

for(i = 0; i<n; i++){     // выводим матрицу с путём

for(j = 0; j < n; j++){

       x = -a[i][j];

       c = x > 2 ? '@' : (x > 1 ? '+' : (x > 0 ? 'O' : '.'));

cout << c;

   }

   cout << endl;

}

}

Кратчайшие пути

Для нахождения кратчайших путей между всеми вершинами графа используется не перебор всех возможностей, что приведет к большому времени работы и потребует больше памяти, а восходящее динамическое программирование, то есть все подзадачи, которые впоследствии понадобятся для решения исходной задачи, просчитываются заранее и затем используются.