Ближайшее число (Матрица) - Помощь студентам - Страница 3

isst · 08.02.2015, 18:50

Цитата:

Сообщение от Poma][a

Фух..
Вот и я присоединился к Вашему обществу..

Код:

#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");

struct st
{
	int x, y, w, ix, iy;
};

struct _step
{
	int x, y;
	friend bool operator == (const _step& a, const _step& b);
	friend bool operator != (const _step& a, const _step& b);
};

bool operator == (const _step& a, const _step& b)
{
	return a.x == b.x && a.y == b.y;
}

bool operator != (const _step& a, const _step& b)
{
	return !(a == b);
}

_step step[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

int main() {
	int n;
	cin >> n;

	vector<vector<int> > v(n + 2, vector<int>(n + 2, -1)), p(n + 2, vector<int>(n + 2, -1)), p1(n + 2, vector<int>(n + 2, -1));
	vector<vector<_step> > stp (n+2, vector<_step> (n+2));
	queue<st> q;
	int k = 0;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
			if (v[i][j] == 0)
			{
				k++;
				p[i][j] = 0;
			}
			else
			{
				st _t;
				_t.x = i; _t.y = j; _t.w = v[i][j];
				_t.ix = i; _t.iy = j;
				q.push(_t);
				_step tt;
				tt.x = _t.x; tt.y = _t.y;
				stp[i][j] = tt;
				p[i][j] = v[i][j];
				p1[i][j] = 0;
			}
		}

	while (!q.empty() && k > 0)
	{
		queue<st> temp;

		while (!q.empty())
		{
			st t = q.front();
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				_step tt = stp[t.ix][t.iy];
		
				if (p[t.x + step[i].x][t.y + step[i].y] > 0 && p1[t.x + step[i].x][t.y + step[i].y] == p1[t.x][t.y] + 1 && stp[t.x + step[i].x][t.y + step[i].y] != tt)
				{
					p[t.x + step[i].x][t.y + step[i].y] = -1;
					st _t;
					_t.x = t.x + step[i].x; _t.y = t.y + step[i].y; _t.w = t.w;
					_t.ix = t.ix; _t.iy = t.iy;
					temp.push(_t); continue;
				}
				else if (p[t.x + step[i].x][t.y + step[i].y] == 0)
				{
					k--;
					p1[t.x + step[i].x][t.y + step[i].y] = p1[t.x][t.y] + 1;
					st _t;
					_t.x = t.x + step[i].x; _t.y = t.y + step[i].y; _t.w = t.w;
					_t.ix = t.ix; _t.iy = t.iy;
					temp.push(_t);
					p[t.x + step[i].x][t.y + step[i].y] = t.w;
					stp[t.x + step[i].x][t.y + step[i].y].x = _t.ix;
					stp[t.x + step[i].x][t.y + step[i].y].y = _t.iy;
					continue;
				}
			}
		}
		q = temp;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << max(0, p[i][j]) << " ";
		cout << endl;
	}
	return 0;
}

Ром, Спасибо огромное, тестил на informatics, все работает. Спасибо, что помог.

FPaul · 08.02.2015, 19:37

И я своё опубликую.
Здесь приведено только решение Poma][a, поэтому сравнение с ним. У меня много проще алгоритм, без динамического программирования, обычный перебор. Отсюда и в 10 раз меньшее быстродействие.
"Чудная" работа с матрицами из-за ограничений TurboPascal (на сайте именно он) по динамическим массивам (их там нет). Можно обойтись и максимальными размерами, но тогда потребление памяти возростёт с 60КБ до 1200КБ.

Код:

program Pas_0621;

const
  NN = 200;
type
  TElement = longint;
  TDynMatrix = array[0..(MaxInt div sizeof(TElement)) - 1] of TElement;
  PDynMatrix = ^TDynMatrix;
  TMatrix  = array[0..NN - 1, 0..NN - 1] of TElement;

  procedure WavesFromStone(const a: TDynMatrix; b: PDynMatrix; n, Ic, Jc: integer);
  var
    i, j, k, r: integer;
    Count: integer;
    ij: integer;
    I_Jx:  integer; {индексы в массиве по которым расположен единственное число в кольце}
    InMatrix: boolean;
  begin
    Count := 0;
    k := 1;
    repeat
      InMatrix := False;
      for r := 0 to k - 1 do
      begin
        {вправо вверх}
        i := Ic - r;
        j := Jc + r - k;
        if not ((i < 0) {or (i >= n)} or (j < 0) or (j >= n)) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
        {вправо вниз}
        i := Ic + r - k;
        j := Jc + r;
        if not ((i < 0) or (i >= n) {or (j < 0)} or (j >= n)) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
        {влево вниз}
        i := Ic + r;
        j := Jc - r + k;
        if not ({(i < 0) or} (i >= n) or (j < 0) or (j >= n)) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
        {влево вверх}
        i := Ic - r + k;
        j := Jc - r;
        if not ((i < 0) or (i >= n) or (j < 0) {or (j >= n)}) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
      end; {for r}
      {увеличение расстояния}
      Inc(k);
    until (Count > 0) or (not InMatrix);
    if Count = 1 then
      b^[Ic * n + Jc] := b^[I_Jx];
  end;

var
  i, j: integer;
  a, b: PDynMatrix;
  n: integer;
begin
  Assign(input, 'input.txt');
  Reset(input);
  Assign(output, 'output.txt');
  Rewrite(output);
  {ввод исходных данных}
  readln(n);
  GetMem(a, sqr(n) * sizeof(TElement));
  GetMem(b, sqr(n) * sizeof(TElement));
  for i := 0 to n - 1 do
  begin
    for j := 0 to n - 1 do
      Read(a^[i * n + j]);
    readln;
  end;
  {b^:=a^}
  for i := 0 to sqr(n) - 1 do
    b^[i] := a^[i];
  {решение}
  for i := 0 to pred(n) do
  begin
    for j := 0 to pred(n) do
    begin
      if a^[i * n + j] = 0 then
        WavesFromStone(a^, b, n, i, j);
    end;
  end;
  {вывод результатов}
  for i := 0 to pred(n) do
  begin
    for j := 0 to pred(n) do
      Write(b^[i * n + j]: 3, ' ');
    writeln;
  end;
  FreeMem(b, sqr(n) * sizeof(TElement));
  FreeMem(a, sqr(n) * sizeof(TElement));
  Close(output);
end.

isst · 08.02.2015, 19:51

Цитата:

Сообщение от FPaul

И я своё опубликую.
Здесь приведено только решение Poma][a, поэтому сравнение с ним. У меня много проще алгоритм, без динамического программирования, обычный перебор. Отсюда и в 10 раз меньшее быстродействие.
"Чудная" работа с матрицами из-за ограничений TurboPascal (на сайте именно он) по динамическим массивам (их там нет). Можно обойтись и максимальными размерами, но тогда потребление памяти возростёт с 60КБ до 1200КБ.

Код:

program Pas_0621;

const
  NN = 200;
type
  TElement = longint;
  TDynMatrix = array[0..(MaxInt div sizeof(TElement)) - 1] of TElement;
  PDynMatrix = ^TDynMatrix;
  TMatrix  = array[0..NN - 1, 0..NN - 1] of TElement;

  procedure WavesFromStone(const a: TDynMatrix; b: PDynMatrix; n, Ic, Jc: integer);
  var
    i, j, k, r: integer;
    Count: integer;
    ij: integer;
    I_Jx:  integer; {индексы в массиве по которым расположен единственное число в кольце}
    InMatrix: boolean;
  begin
    Count := 0;
    k := 1;
    repeat
      InMatrix := False;
      for r := 0 to k - 1 do
      begin
        {вправо вверх}
        i := Ic - r;
        j := Jc + r - k;
        if not ((i < 0) {or (i >= n)} or (j < 0) or (j >= n)) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
        {вправо вниз}
        i := Ic + r - k;
        j := Jc + r;
        if not ((i < 0) or (i >= n) {or (j < 0)} or (j >= n)) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
        {влево вниз}
        i := Ic + r;
        j := Jc - r + k;
        if not ({(i < 0) or} (i >= n) or (j < 0) or (j >= n)) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
        {влево вверх}
        i := Ic - r + k;
        j := Jc - r;
        if not ((i < 0) or (i >= n) or (j < 0) {or (j >= n)}) then
        begin
          InMatrix := True;
	  ij:=i * n + j;
          if a[ij] <> 0 then
          begin
            Inc(Count);
            I_Jx := ij;
          end;
        end;
      end; {for r}
      {увеличение расстояния}
      Inc(k);
    until (Count > 0) or (not InMatrix);
    if Count = 1 then
      b^[Ic * n + Jc] := b^[I_Jx];
  end;

var
  i, j: integer;
  a, b: PDynMatrix;
  n: integer;
begin
  Assign(input, 'input.txt');
  Reset(input);
  Assign(output, 'output.txt');
  Rewrite(output);
  {ввод исходных данных}
  readln(n);
  GetMem(a, sqr(n) * sizeof(TElement));
  GetMem(b, sqr(n) * sizeof(TElement));
  for i := 0 to n - 1 do
  begin
    for j := 0 to n - 1 do
      Read(a^[i * n + j]);
    readln;
  end;
  {b^:=a^}
  for i := 0 to sqr(n) - 1 do
    b^[i] := a^[i];
  {решение}
  for i := 0 to pred(n) do
  begin
    for j := 0 to pred(n) do
    begin
      if a^[i * n + j] = 0 then
        WavesFromStone(a^, b, n, i, j);
    end;
  end;
  {вывод результатов}
  for i := 0 to pred(n) do
  begin
    for j := 0 to pred(n) do
      Write(b^[i * n + j]: 3, ' ');
    writeln;
  end;
  FreeMem(b, sqr(n) * sizeof(TElement));
  FreeMem(a, sqr(n) * sizeof(TElement));
  Close(output);
end.

FPaul, не хочу показаться предирой, но вот Ваше решение не срабатывает на одном из тестов (к сожалению, не могу знать, на каком). Проходит 15 из 16.

Аватар · 08.02.2015, 19:52

Если сайт acmp по Ромахиной ссылке, то там компилятор от D7

Код:

program Project1;

{$APPTYPE CONSOLE}

var n,i,j,k,m: Smallint;
    a: array of array of Integer;
    v,c1,c2: Integer;

function TestCell(pi,pj: Integer): Integer;
begin
  if (pi<0) or (pi>=n) or (pj<0) or (pj>=n) then Result:=0
  else begin
    Result:=Ord(a[pi,pj]>0);
    if Result=1 then v:=a[pi,pj];
    Inc(c2);
  end;
end;

begin
  Assign(input,'input.txt');
  Reset(input);
  Readln(n);
  SetLength(a,n,n);
  for i:=0 to n-1 do begin
    for j:=0 to n-1 do Read(a[i,j]);
    Readln;
  end;

  Assign(output, 'output.txt');
  Rewrite(output);
  for i:=0 to n-1 do begin
    for j:=0 to n-1 do begin
      if a[i,j]=0 then begin
        k:=1; c1:=0;
        repeat
          c2:=0;
          for m:=0 to k do begin
            c1:=c1+TestCell(i-k+m,j+m)+TestCell(i+m,j-k+m);
            if (m>0) and (m<k) then c1:=c1+TestCell(i-k+m,j-m)+TestCell(i+m,j+k-m);
            if c1>1 then Break;
          end;
          if c1=1 then a[i,j]:=-v;
          Inc(k);
        until (c2=0) or (c1>0);
      end;
      Write(Abs(a[i,j]),' ');
    end;
    Writeln;
  end;

end.

FPaul · 08.02.2015, 19:55

Да, по той ссылке. Но компилятор ругался на dword, пока не заменил на longint.
Что-то я не так сделал...

Poma][a · 08.02.2015, 19:58

QWord бы зашел

Аватар · 08.02.2015, 20:00

DWORD в юните Types , а longint в System, вот и вся беда

Этот подход можно по времени оптимизировать, имея ввиду тот факт, что если известно минимальное расстояние (R), то у соседней (слева, справа, сверху и снизу) оно может быть R-1, R и R+1. Код и память больше станут

FPaul · 08.02.2015, 20:03

Проверил - нет. TurboPascal. Хотя в разделе работа в системе Borland Delphi 7.0
------------
Прошу прощения. Думал, что FPC по составу модулей схож с Delphi.

Poma][a · 08.02.2015, 20:04

Не.. Не турбо там.. Бахните, например, array of Integer.. и тамошний компиль ругать не будет, чесн слово

FPaul · 08.02.2015, 20:10

Это открытые массивы. Они в TP7 ещё были. Вот SetLength - уже дельфи.
Аватар уже объяснил, в чём моя ошибка - незнание различий между Delphi и FPC.

08.02.2015, 20:00	#27
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	DWORD в юните Types , а longint в System, вот и вся беда Этот подход можно по времени оптимизировать, имея ввиду тот факт, что если известно минимальное расстояние (R), то у соседней (слева, справа, сверху и снизу) оно может быть R-1, R и R+1. Код и память больше станут Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию Последний раз редактировалось Аватар; 08.02.2015 в 20:06.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Найти ближайшее к какому - нибудь целому	Asya7	Паскаль, Turbo Pascal, PascalABC.NET	8	15.01.2015 02:00
Prolog.Ближайшее значение в списке	Lisёноk	Помощь студентам	2	28.11.2013 16:36
Ближайшее и наименьшее к n из двух чисел	turtles	Общие вопросы по Java, Java SE, Kotlin	2	25.08.2011 16:19
Натуральное число n. Матрица	lexx007	Помощь студентам	1	20.12.2008 22:35

08.02.2015, 19:55	#25
FPaul Форумчанин Регистрация: 25.01.2015 Сообщений: 474	Да, по той ссылке. Но компилятор ругался на dword, пока не заменил на longint. Что-то я не так сделал...

08.02.2015, 19:58	#26
Poma][a Новичок Джуниор Регистрация: 11.10.2011 Сообщений: 3,882	QWord бы зашел

08.02.2015, 20:03	#28
FPaul Форумчанин Регистрация: 25.01.2015 Сообщений: 474	Проверил - нет. TurboPascal. Хотя в разделе работа в системе Borland Delphi 7.0 ------------ Прошу прощения. Думал, что FPC по составу модулей схож с Delphi.

08.02.2015, 20:04	#29
Poma][a Новичок Джуниор Регистрация: 11.10.2011 Сообщений: 3,882	Не.. Не турбо там.. Бахните, например, array of Integer.. и тамошний компиль ругать не будет, чесн слово

08.02.2015, 20:10	#30
FPaul Форумчанин Регистрация: 25.01.2015 Сообщений: 474	Это открытые массивы. Они в TP7 ещё были. Вот SetLength - уже дельфи. Аватар уже объяснил, в чём моя ошибка - незнание различий между Delphi и FPC.