Задача - определение числа комнат и их площади

[Chosen One]

помогите написать прогу=) пжалуста, а то сдать надо бы уже давненько

[0xDEADBEEF]

Поиск связанных компонент в графе. Преобразование карты почти тривиальное.

Сори, но мне чета лень делать(

[Chosen One]

0xDEADBEEF

а может все-таки стоит попробовать) Я ж не просто так тему отписал тут)

[Gros]

Идея решения:

Данную задачу можно решить используя метод перебора с возвратом.

Используя массив координат перемещения, смотрим, где отсутствуют стены, для каждой клетки, и последовательно двигаемся в ту клетку, в которую

возможно, предварительно помечая клетку, в которой уже были. Если мы зашли в тупик, то возвращаемся в клетку, из которой вышли. Одновременно считаем количество клеток в каждой комнате. Когда происходит возврат в начальную точку движения, делаем всю комнату просмотренной (при помощи массива логического типа). Затем ищем клетку, в которой ещё не были и делаем её начальной точкой движения.

Uses crt;

Const n=100;

X:array[0..3]of -1..1=(0,-1,0,1); {массив координат перемещения по

Y:array[0..3]of -1..1=(-1,0,1,0); клеткам. Индекс элемента массива

Type Mas=array[0..n,0..n]of Integer; соответствует степени двойки}

var A:mas;

B:array[0..n,0..n]of Boolean;

m,p,col,rooms,indexX,indexY:integer;

procedure Init(Z:string); {заполнение из входного файла массива, представляющего цифровую карту музея}

Var f:text;

i,j:integer;

Begin

Assign(f,z);

Reset(f);

ReadLn(f,m,p);

For i:=1 to m do

begin

For j:=1 to p do

Read(f,A[i,j]);

ReadLn(f);

end;

FillChar(B,SizeOf(,true);

For i:=1 to m do

For j:=1 to p do

B[i,j]:=false;

Close(f);

end;

function Degree2(i:integer):integer; {функция, вычисляющая i–ую степень двойки}

var j,t:integer;

begin

t:=1;

For j:=1 to i do

t:=t*2;

Degree2:=t;

end;

Procedure Solve(i,j:integer);

Var k:integer;

begin

k:=3;

While k>=0 do

begin

If A[i,j] направлении}

begin

If not B[i+X[k],j+Y[k]] then {определяем, заходили ли мы в клетку ранее}

begin

Inc(col); {учитываем клетку в общей площади комнаты}

B[i,j]:=true; {отмечаем, что в текущей клетке мы уже были}

Solve(i+X[k],j+Y[k]); {переходим в следующую клетку}

B[i,j]:=False; {делаем клетку, в которой последний раз были не просмотренной, чтобы рассмотреть другие варианты хода из неё в другую клетку}

end;

end

Else A[i,j]:=A[i,j]-Degree2(k);

Dec(k);

end;

end;

procedure Prosmotr; {данная процедура отмечает уже просмотренную комнату}

var i,j:integer;

begin

For i:=1 to m do

For j:=1 to p do

If A[i,j]=0 then B[i,j]:=True;

end;

begin

clrscr;

Init('A:museum.txt');

rooms:=0;

For indexX:=1 to m do {ищем ранее не просмотренную клетку}

For indexY:=1 to p do

If not B[indexX,indexY] Then

begin

col:=1;

Inc(rooms);

Solve(indexX,indexY);

Write(Col,' '); {вывод площади только что просмотренной комнаты}

Prosmotr;

end;

WriteLn;

WriteLn(rooms); {вывод количества комнат}

readkey;

end.

держи...

[FunlOvEe]

Помогите написать прогу или напишите идею решения данной задачи.

Совмещение ломаных. Две ломаные построены по ребрам сеточной области с целочисленными координатами. Требуется составить алгоритм—программу проверки совпадения двух ломаных, составленных из отрезков, с точностью до параллельного переноса и поворота на 90°, 180°, 270°. Исходные данные — число отрезков ломаных и значения координат их концов — определяются в текстовом файле. Выходной файл результатов должен содержать признак 1, если ломаные совпадают, и 0 — в противном случае.

Пример файла исходных данных:

4 — количество отрезков первой ломаной

0 0 1 0 3 0 2 0 1 0 2 0 3 0 3 1

2 — количество отрезков второй ломаной

1 1 1 4 0 4 1 4

Пример файла результатов:

1 — ломаные совпадают.

[0xDEADBEEF]

Gros

Почему мне так хочется матерится?

#include
#include
#include

using namespace std;

int N = 0, M = 0;
int** maze = NULL;
bool** visited = NULL;

void input() {
ifstream fin("input.txt");

if (!fin) {
cerr << "Can't open input file!" << endl;
exit(-1);
}

fin >> N >> M;

maze = new int*[N];
visited = new bool*[N];

for (int i = 0; i < N; ++i) {
maze[i] = new int[M];
visited[i] = new bool[M];
fill(visited[i], visited[i] + M, false);
for (int j = 0; j < M; ++j) {
fin >> maze[i][j];
}
}
fin.close();
}

#define CAN_GO_WEST(row,col) ((col>0) && !(maze[row][col] & 1) && !visited[row][col-1])
#define CAN_GO_NORTH(row,col) ((row>0) && !(maze[row][col] & 2) && !visited[row-1][col])
#define CAN_GO_EAST(row,col) ((col#define CAN_GO_SOUTH(row,col) ((row
int dfs(int row, int col) {
int cnt = 1;
visited[row][col] = true;
if (CAN_GO_WEST(row, col)) {
cnt += dfs(row, col - 1);
}
if (CAN_GO_NORTH(row, col)) {
cnt += dfs(row - 1, col);
}
if (CAN_GO_EAST(row, col)) {
cnt += dfs(row, col + 1);
}
if (CAN_GO_SOUTH(row, col)) {
cnt += dfs(row + 1, col);
}
return (cnt);
}

int main() {
input();
vector ans;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (!visited[i][j])
ans.push_back(dfs(i, j));
}
}

cout < for (int i = 0; i < (int) ans.size(); ++i) {
cout < }
cout < return 0;
}

[L0K1]

0xDEADBEEF

Зачет... =)

[Gros]

Gros

Почему мне так хочется матерится?

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

[Chosen One]

Gros

да-да, ты прав!

[0xDEADBEEF]

Пардон, паскаля уже не помню(

А мат за бэктрекинг, субьективно непонятный

[Gros]

0xDEADBEEF я его не писал, я сделал малое CTRL+C - CTRL+V...

[FunlOvEe]

Помогите написать прогу или напишите идею решения данной задачи.

Совмещение ломаных. Две ломаные построены по ребрам сеточной области с целочисленными координатами. Требуется составить алгоритм—программу проверки совпадения двух ломаных, составленных из отрезков, с точностью до параллельного переноса и поворота на 90°, 180°, 270°. Исходные данные — число отрезков ломаных и значения координат их концов — определяются в текстовом файле. Выходной файл результатов должен содержать признак 1, если ломаные совпадают, и 0 — в противном случае.

Пример файла исходных данных:

4 — количество отрезков первой ломаной

0 0 1 0 3 0 2 0 1 0 2 0 3 0 3 1

2 — количество отрезков второй ломаной

1 1 1 4 0 4 1 4

Пример файла результатов:

1 — ломаные совпадают.

мб кому-нибудь пригодится

#include
#include
#include
#include
#include
using namespace std;

struct decart
{
int x;
int y;
};

int cos4[] = {1, 0, -1, 0};
int sin4[] = {0, 1, 0, -1};
int n1, n2;
struct decart *line1, *line2, *nline1, *nline2;

// true, если три точки образуют прямую линию
bool isline(struct decart *p)
{
return (p[0].x * p[1].y + p[1].x * p[2].y + p[2].x * p[0].y) -
(p[0].y * p[1].x + p[1].y * p[2].x + p[2].y * p[0].x) == 0;
}

// return: true - присоединение найденного отрезка слева
// false - присоединение найденного отрезка справа
bool isleft(struct decart *src, int x0, int y0, int x1, int y1, struct decart *result, int cnt)
{
bool left;
struct decart *begin;

left = true;
begin = src;

for(;
{
if(src[0].x == x0 && src[0].y == y0)
{
result[0] = src[1];
break;
}
if(src[0].x == x1 && src[0].y == y1)
{
result[0] = src[1];
left = false;
break;
}
if(src[1].x == x0 && src[1].y == y0)
{
result[0] = src[0];
break;
}
if(src[1].x == x1 && src[1].y == y1)
{
result[0] = src[0];
left = false;
break;
}
src += 2;
}
memmove(src, src + 2, (cnt * 2 - 2 - (src - begin)) * sizeof(struct decart));
return(left);
}

// Склеивание отдельных отрезков в сплошную ломаную
int sort_line(struct decart *src, struct decart *dest, int cnt)
{
struct decart *begin, tmp;

begin = dest;
dest[0] = src[0];
dest[1] = src[1];
dest += 2;
src += 2;

while(--cnt)
{
if(isleft(src, begin[0].x, begin[0].y, dest[-1].x, dest[-1].y, &tmp, cnt))
{
memmove(begin + 1, begin, (dest - begin) * sizeof(struct decart));
begin[0] = tmp;
}
else
{
dest[0] = tmp;
}
++dest;
}

return(dest - begin);
}

// Выбросить среднюю точку из трех точек, если эти
// три точки располагаются на одной линии
int del_punkt(struct decart *p, int cnt)
{
int i;
struct decart *tmp;
bool yes_delete;

do
{
yes_delete = false;
for(tmp = p,i = cnt - 2; i; --i,++tmp)
{
if(isline(tmp))
{
memmove(tmp + 1, tmp + 2, (cnt - 2 - (tmp - p)) * sizeof(struct decart));
--cnt;
yes_delete = true;
break;
}
}
} while(yes_delete);
return(cnt);
}

bool eq_line(struct decart *line1, struct decart *line2, int cnt, int step)
{
int i, j, k, x, y;

for(i = 0; i < 4; ++i)
{
for(j = k = 0; j < cnt; ++j,k += step)
{
x = line1[k].x * cos4[i] + line1[k].y * sin4[i];
y = -line1[k].x * sin4[i] + line1[k].y * cos4[i];
if(line2[k].x != x || line2[k].y != y)
break;
}
if(j == cnt)
return(true);
}
return(false);
}

void input(void)
{
int i;
ifstream fin("input.txt");

if(!fin)
{
cout << "Cant open the file\n";
cout << "Press any key...";
getch();
exit(0);
}

fin >> n1;
line1 = new struct decart[n1 * 2];
nline1 = new struct decart[n1 + 1];

for(i = 0; i < n1 * 2; ++i)
{
fin >> line1[i].x >> line1[i].y;
}

fin >> n2;
line2 = new struct decart[n2 * 2];
nline2 = new struct decart[n2 + 1];

for(i = 0; i < n2 * 2; ++i)
{
fin >> line2[i].x >> line2[i].y;
}
}

void output(char c)
{
delete[] line1;
delete[] line2;
delete[] nline1;
delete[] nline2;
ofstream fout("output.txt");
fout << c;
}

int main(int argc, char* argv[])
{
int i, x1, x2, y1, y2;

input();
n1 = sort_line(line1, nline1, n1);
n2 = sort_line(line2, nline2, n2);

n1 = del_punkt(nline1, n1);
n2 = del_punkt(nline2, n2);

if(n1 != n2)
{
output('0');
cout<<"0 Press any key...";
//getch();
return(0);
}

// Сдвиг по левому краю
x1 = nline1[0].x;
y1 = nline1[0].y;
x2 = nline2[0].x;
y2 = nline2[0].y;
for(i = 0; i < n1; ++i)
{
nline1[i].x -= x1;
nline1[i].y -= y1;
nline2[i].x -= x2;
nline2[i].y -= y2;
}

if(eq_line(nline1 + 1, nline2 + 1, n1 - 1, +1))
{
output('1');
cout<<"1 Press any key...";
//getch();
return(0);
}

// Сдвиг по правому краю
x1 = nline1[n1 - 1].x;
y1 = nline1[n1 - 1].y;
for(i = 0; i < n1; ++i)
{
nline1[i].x -= x1;
nline1[i].y -= y1;
}

if(eq_line(nline1 + n1 - 2, nline2 + n1 - 2, n1 - 1, -1))
{
output('1');
cout<<"1 Press any key...";
//getch();
return(0);
}

output('0');
cout<<"0 Press any key...";
//getch();
return 0;
}

#include