В некоторых клетках поля N * M расставлены фишки.
Выбрать ромб, который полностью лежит на поле и содержит наибольшее
количество фишек. Дополнительное условие: в ромбе не должно быть ни
единой пары фишек, которые стоят в клетках с общей стороной.
Формат входного файла
В первой строчке заданы два числа N и M (1 ≤ N, M ≤ 3000). Следующие
N строк содержат по M символов каждый. Символом ‘*’ обозначает фишку, а
символом ‘.’ – свободную клетку.
Формат выходного файла
Выведите единственное число K – количество фишек в найденном ромбе.
Пример входного файла:
2 3
...
..*
Стандартный вывод:
1
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <iostream>
#include <string>
#include <fstream>
#include <clocale>
#include <ctime>
#include <time.h>
using namespace std;
void main()
{
ifstream is;
ofstream os;
setlocale(LC_ALL, "Rus");//объявление русского языка
is.open("input.txt"); // открытие файла input
//unsigned int start_time = clock(); // Засекает время с момента открытия файла input
int a, b;//объявление переменных
int count = 0, x = 0, y = 0;//объявление переменных и придаем им значений 0
//объявляем переменные и придаем им ложное значение
bool Answer = false;
bool end = false;
is >> a >> b;//берем значения из файла
char **map = new char *[a];//операция выделения свободной памяти под создаваемый объект
for (int i = 0; i <a; i++) {
map[i] = new char[b];
for (int j = 0; j < b; j++)//берем переменные из файла
is >> map[i][j];
}
is.close();//закрываем файл
//выводим карту
cout << "POle: " << endl;
//начало цикла(условие)
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++)
cout <<" "<< map[i][j];//тело цикла
cout << endl;
}
cout << endl << endl;//
//проход по карте
do { //начало цикла do while
//заполнение матрицы символами
if (map[x][y] == '*') { count++; map[x][y] = '*'; };
if (map[x][y + 1] != '*' && y <= b - 1) { y++; }
else if (x < a - 1 && !(map[x + 1][y] == '*')) { count++; x++; }
else if (x == a - 1 && y == b - 1) { Answer = true; }
} while (!Answer);//условие выполнения цикла
do { //начало цикла do while
//заполнение матрицы символами
if (map[x][y] == '*' && !((x == a - 1 && y == b - 1) || (x == 0 && y == 0))) { count++; map[x][y] = '*'; };
if (!(map[x][y - 1] == '.') && y > 0) {
y--;
}
else if (x > 0 && !(map[x - 1][y] == '*')) { x--; }
else if (x == 0 && y == 0) { end = true; }
} while (!end);//условие выполнения цикла
//вывод кол-ва пройденых мест
cout << "Кол-во фишек в найденном ромбе: " << endl;
cout << count << endl << endl;
//вывод карты с пройденными местами,которые отмечены +
//cout << "Места, которые были посещены (+): " << endl;
//начало цикла(условие)
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++)
// cout <<" "<<map[i][j];//тело цикла(выводит карту,где пройденные места отмечены)
cout << endl;
}
cout << endl << endl;
os.open("output.txt");//открытие файла output
//очищаем память массива
for (int i = 0; i < a; i++)
delete[] map[i];
delete[] map;
os << count;//ответ записываем в файл
//unsigned int end_time = clock(); // Конец счета времени
//unsigned int search_time = end_time - start_time; // Считаем разницу между конечным показателем времени и начальным
//cout << "Время: " << search_time / 1000.0 << endl;//вывод времени
os.close();//закрытие файла output
system("pause");//пауза
} |
|
(
