//вместо
int **array = new int* [row_count];
for (int i = 0; i < row_count; i++) array = new int [col_count];
//используйте
int *array = new int [row_count * col_count];
//при этом обратиться к элементу массива array[j] можно так:
array[i*col_count + j] = ...
C++ передача копии массива в функцию
Подскажите, пожалуйста, как передать в функцию копию массива?
Зараннее спасибо=)
Зараннее спасибо=)
Ну или хотя бы как быстро создать копию двумерного массива... Кроме того, замечено, что с использованием memcpy и memmove образец, с к-рого делалась копия, тоже изменяется с изменением копии.
std::vector не подойдет?
[QUOTE="FloyDos"]Кроме того, замечено, что с использованием memcpy и memmove образец, с к-рого делалась копия, тоже изменяется с изменением копии[/QUOTE]Код покажите
ЗЫ А вообще, какая стоит задача? Зачем передавать именно копию?
[QUOTE="FloyDos"]Кроме того, замечено, что с использованием memcpy и memmove образец, с к-рого делалась копия, тоже изменяется с изменением копии[/QUOTE]Код покажите
ЗЫ А вообще, какая стоит задача? Зачем передавать именно копию?
Необходимо, чтоб после передачи массива в пользов-ю функцию массив в главной функции не изменился. Ведь обычно мы передаем указатель на массив, а в моем случае нужно передать копию массива. вот в чем соль=)так понятно?дело в том, что создавать копию массива вручную в доп функции занимает много времени, ибо массив достаточно большой и функция вызывается много раз.
Цитата: FloyDos
Необходимо, чтоб после передачи массива в пользов-ю функцию массив в главной функции не изменился.
Вот я и спрашиваю, нафига это нужно.
для решения старой олимпиадной задачи касательно четырехсвязных областей. в цикле необх работать с одним и тем же массивом областей. при обработке естессно массив несколько изменяется, тчто надо его в первозданный вид все время возвращать.если интересует могу полный текст задачи вывесить=)
а вообще по-моему эта проблема может много где возникнуть.
а вообще по-моему эта проблема может много где возникнуть.
Цитата:
если интересует могу полный текст задачи вывесить
И текст надо, и ваш код надо - поскольку телепаты тут пока не встречались.
Поскольку на "сферическое копирование массива в вакууме" могу дать только один совет - используйте вектор
Структуры из одинаковых кубиков, зажимая между двумя прозрачными пластинами плексигласа, окунают в воду. Кубики имеют единичный размер и состоят из материала, пропускающего воздух, но не пропускающего воду.
Когда структуру погружают в воду, вода заполняет всё свободное пространство внутри структуры, которое она может заполнить. Вода может распространяться из каждой ячейки в пустые ячейки, смежные с данной по горизонтали, вертикали или диагонали. сами кубики для воды непроницаемы.
X..
.X. Вода может перетекать из одной области в другую
..X
X..
XXX Вода не может перетекать из одной области в другую
...
В приведённых выше примерах кубики обозначены символами “X”, пустые ячейки конструкции – символами “.”. В первом примере две пустые области конструкции связаны, и вода может перетекать из левой нижней области в правую верхнюю, и наоборот. Во втором примере две пустые области не связаны.
После «замачивания» конструкция аккуратно (и строго вертикально) вынимается из воды. Вода вытекает изо всех дырок на нижней и боковых гранях конструкции. Кроме того, из-за гидростатического давления уровень воды во всех оставшихся внутри конструкции «лужах» не может быть выше, чем дно самой нижней дырки, через которую вода может вытекать.
XXXXXXXXXXX XXXXXXXXXXX
XX......XXX X......X..X
XXX.XXXXX.X X.XXXX~X..X
X...X.XXXXX X.X~~~~X...
X.X.X...X.X X~XXXXXX~~X
X.X~X~X.X.X X~~~~~~X~~X
X.X~~~X...X X~~~~~~~~~X
X.XXXXXXX.X XXXXXXXXXXX
В этих примерах символами “~” обозначено максимальное количество воды, которая может остаться внутри конструкции.
Каждая такая конструкция может сохранять внутри себя различное количество воды, в зависимости от того, каким концом её погружают в воду. Возможны 4 способа погружения (и вытаскивания). При этом боковые плексигласовые грани всегда вертикальны).
Вход: В первой строке входного файла записаны целые числа H и W – размеры конструкции (1 <= H, W <= 40). В следующих H строках записано по W символов: ‘X’ обозначает кубик, ‘.’ обозначает пустую ячейку.
Выход: Записать в выходной файл в порядке не возрастания четыре числа – объём воды оставшейся внутри конструкции после «замачивания» в воде и вытаскивания при четырёх возможных ориентациях конструкции.
Примеры входа и выхода:
water.in
8 11
XXXXXXXXXXX
XX......XXX
XXX.XXXXX.X
X...X.XXXXX
X.X.X...X.X
X.X.X.X.X.X
X.X...X...X
X.XXXXXXX.X
water.out
31 5 4 1
Когда структуру погружают в воду, вода заполняет всё свободное пространство внутри структуры, которое она может заполнить. Вода может распространяться из каждой ячейки в пустые ячейки, смежные с данной по горизонтали, вертикали или диагонали. сами кубики для воды непроницаемы.
X..
.X. Вода может перетекать из одной области в другую
..X
X..
XXX Вода не может перетекать из одной области в другую
...
В приведённых выше примерах кубики обозначены символами “X”, пустые ячейки конструкции – символами “.”. В первом примере две пустые области конструкции связаны, и вода может перетекать из левой нижней области в правую верхнюю, и наоборот. Во втором примере две пустые области не связаны.
После «замачивания» конструкция аккуратно (и строго вертикально) вынимается из воды. Вода вытекает изо всех дырок на нижней и боковых гранях конструкции. Кроме того, из-за гидростатического давления уровень воды во всех оставшихся внутри конструкции «лужах» не может быть выше, чем дно самой нижней дырки, через которую вода может вытекать.
XXXXXXXXXXX XXXXXXXXXXX
XX......XXX X......X..X
XXX.XXXXX.X X.XXXX~X..X
X...X.XXXXX X.X~~~~X...
X.X.X...X.X X~XXXXXX~~X
X.X~X~X.X.X X~~~~~~X~~X
X.X~~~X...X X~~~~~~~~~X
X.XXXXXXX.X XXXXXXXXXXX
В этих примерах символами “~” обозначено максимальное количество воды, которая может остаться внутри конструкции.
Каждая такая конструкция может сохранять внутри себя различное количество воды, в зависимости от того, каким концом её погружают в воду. Возможны 4 способа погружения (и вытаскивания). При этом боковые плексигласовые грани всегда вертикальны).
Вход: В первой строке входного файла записаны целые числа H и W – размеры конструкции (1 <= H, W <= 40). В следующих H строках записано по W символов: ‘X’ обозначает кубик, ‘.’ обозначает пустую ячейку.
Выход: Записать в выходной файл в порядке не возрастания четыре числа – объём воды оставшейся внутри конструкции после «замачивания» в воде и вытаскивания при четырёх возможных ориентациях конструкции.
Примеры входа и выхода:
water.in
8 11
XXXXXXXXXXX
XX......XXX
XXX.XXXXX.X
X...X.XXXXX
X.X.X...X.X
X.X.X.X.X.X
X.X...X...X
X.XXXXXXX.X
water.out
31 5 4 1
А вот кусок кода:
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++){
if (color[j]==water){
result[res]++;
putinnext(color,i,j,i,j,res);
if(color[j]==away)
result[res]--;
clear(color,H,W);
}
}
void putinnext(char **col, int x0, int y0, int x, int y, int res){
bool ff[4];
if (col[x][y]==hole)
col[x0][y0]=away;
else{
col[x][y]=done;
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
}
}
Цитата:
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++){
if (color[j]==water){
result[res]++;
putinnext(color,i,j,i,j,res);
if(color[j]==away)
result[res]--;
clear(color,H,W);
}
}
преобразование массива происходит в функции putinnext:
Цитата:
void putinnext(char **col, int x0, int y0, int x, int y, int res){
bool ff[4];
if (col[x][y]==hole)
col[x0][y0]=away;
else{
col[x][y]=done;
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
}
}
кстати , как раз функция clear и тормозит весь процесс: приходится заново "перекрашивать" использованные клетки в исходный цвет.
Цитата:
кстати , как раз функция clear и тормозит весь процесс
Это вам профилировщик сказал? Или вы просто предполагаете?
- Судя по тому, что вы сказали, эта функция просто перебирает ячейки, присваивая некоторым из них определенные значения. При чем тут тогда копирование массива при передаче?
- Сильно тормозить программу может выделение/освобождение памяти в цикле. В этом случае просто выделите память заранее, до цикла. Плюс вместо двумерного массива можно использовать одномерный:
Код:
ЗЫ Говорите, что именно clear тормозит, и не приводите ее код. Говорите, что memcpy работает странно и не приводите код, который использует эту самую memcpy...
Цитата:
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
const char water='w';
const char stone='X';
const char hole='h';
const char done = 'D';
const char away = 'A';
const int a[8][2]={
{-1,-1},
{-1,0},
{-1,1},
{0,1},
{1,1},
{1,0},
{1,-1},
{0,-1}};
const bool b[4][4]={
{1,0,0,0},
{0,1,0,0},
{0,0,1,0},
{0,0,0,1}
};
void putinnext(char **col,int x0,int y0,int x,int y, int res);
void paintwithwater(char **col,int x,int y);
void makehole(char **col,int h, int w, int re);
void copyy(char** dest,char **sour, int h, int w);
void clear(char **col,int h,int w);
void sort(int *f);
int imin(int *f, int beg);
int _tmain(int argc, _TCHAR* argv[])
{
ifstream inp("water.in");
ofstream outp("water.out");
int W,H;
inp>>H>>W;
//1)make array
char **color = new char*[H+2];
for (int i=0;i<H+2;i++){
color=new char[W+2];
for (int j=0;j<W+2;j++)
color[j]='X';
}
//2)input '.' and 'X' and put holes
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++){
inp>>color[j];
if ((color[j]=='.')&&((i==1)||(j==1)||(i==H)||(j==W)))
color[j]=hole;
}
//3)paint with Water all through holes
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++)
if (color[j]==hole)
paintwithwater(color,i,j);
//results
int result[4];
for (int res=0;res<4;res++){
makehole(color,H,W,res);
result[res]=0;
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++){
if (color[j]==water){
result[res]++;
putinnext(color,i,j,i,j,res);
if(color[j]==away)
result[res]--;
clear(color,H,W);
}
}
}
sort(result);
for (int i=0;i<4;i++)
outp<<result<<" ";
outp.close();
return 0;
}
void putinnext(char **col, int x0, int y0, int x, int y, int res){
bool ff[4];
if (col[x][y]==hole)
col[x0][y0]=away;
else{
col[x][y]=done;
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
}
}
void paintwithwater(char **col,int x,int y){
if (col[x][y]=='.')
col[x][y]=water;
for (int i=0;i<8;i++)
if (col[x+a[0]][y+a[1]]=='.')
paintwithwater(col, x+a[0],y+a[1]);
}
void makehole(char **col,int h, int w, int re){
switch (re){
case 0:
for (int i=2;i<w;i++)
if (col[1]==hole)
col[1]=water;
break;
case 1:
for (int i=2;i<w;i++)
if (col[1]==water)
col[1]=hole;
for (int i=2;i<h;i++)
if (col[1]==hole)
col[1]=water;
break;
case 2:
for (int i=2;i<h;i++)
if (col[1]==water)
col[1]=hole;
for (int i=2;i<w;i++)
if (col[h]==hole)
col[h]=water;
break;
case 3:
for (int i=2;i<w;i++)
if (col[h]==water)
col[h]=hole;
for (int i=2;i<h;i++)
if (col[w]==hole)
col[w]=water;
break;
}
}
void clear(char **col,int h,int w){
for (int i=1;i<h+1;i++)
for (int j=1;j<w+1;j++){
if ((col[j]==done)||(col[j]==away))
col[j]=water;
}
}
void sort (int *f){
for (int i=0;i<4;i++)
swap(f,f[imin(f,i)]);
}
int imin(int *f, int beg){
int m=f[beg];
int im=beg;
for (int i=beg+1;i<4;i++)
if (f>=m){
m=f;
im=i;
}
return im;
}
#include <iostream>
#include <fstream>
using namespace std;
const char water='w';
const char stone='X';
const char hole='h';
const char done = 'D';
const char away = 'A';
const int a[8][2]={
{-1,-1},
{-1,0},
{-1,1},
{0,1},
{1,1},
{1,0},
{1,-1},
{0,-1}};
const bool b[4][4]={
{1,0,0,0},
{0,1,0,0},
{0,0,1,0},
{0,0,0,1}
};
void putinnext(char **col,int x0,int y0,int x,int y, int res);
void paintwithwater(char **col,int x,int y);
void makehole(char **col,int h, int w, int re);
void copyy(char** dest,char **sour, int h, int w);
void clear(char **col,int h,int w);
void sort(int *f);
int imin(int *f, int beg);
int _tmain(int argc, _TCHAR* argv[])
{
ifstream inp("water.in");
ofstream outp("water.out");
int W,H;
inp>>H>>W;
//1)make array
char **color = new char*[H+2];
for (int i=0;i<H+2;i++){
color=new char[W+2];
for (int j=0;j<W+2;j++)
color[j]='X';
}
//2)input '.' and 'X' and put holes
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++){
inp>>color[j];
if ((color[j]=='.')&&((i==1)||(j==1)||(i==H)||(j==W)))
color[j]=hole;
}
//3)paint with Water all through holes
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++)
if (color[j]==hole)
paintwithwater(color,i,j);
//results
int result[4];
for (int res=0;res<4;res++){
makehole(color,H,W,res);
result[res]=0;
for (int i=1;i<H+1;i++)
for (int j=1;j<W+1;j++){
if (color[j]==water){
result[res]++;
putinnext(color,i,j,i,j,res);
if(color[j]==away)
result[res]--;
clear(color,H,W);
}
}
}
sort(result);
for (int i=0;i<4;i++)
outp<<result<<" ";
outp.close();
return 0;
}
void putinnext(char **col, int x0, int y0, int x, int y, int res){
bool ff[4];
if (col[x][y]==hole)
col[x0][y0]=away;
else{
col[x][y]=done;
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
}
}
void paintwithwater(char **col,int x,int y){
if (col[x][y]=='.')
col[x][y]=water;
for (int i=0;i<8;i++)
if (col[x+a[0]][y+a[1]]=='.')
paintwithwater(col, x+a[0],y+a[1]);
}
void makehole(char **col,int h, int w, int re){
switch (re){
case 0:
for (int i=2;i<w;i++)
if (col[1]==hole)
col[1]=water;
break;
case 1:
for (int i=2;i<w;i++)
if (col[1]==water)
col[1]=hole;
for (int i=2;i<h;i++)
if (col[1]==hole)
col[1]=water;
break;
case 2:
for (int i=2;i<h;i++)
if (col[1]==water)
col[1]=hole;
for (int i=2;i<w;i++)
if (col[h]==hole)
col[h]=water;
break;
case 3:
for (int i=2;i<w;i++)
if (col[h]==water)
col[h]=hole;
for (int i=2;i<h;i++)
if (col[w]==hole)
col[w]=water;
break;
}
}
void clear(char **col,int h,int w){
for (int i=1;i<h+1;i++)
for (int j=1;j<w+1;j++){
if ((col[j]==done)||(col[j]==away))
col[j]=water;
}
}
void sort (int *f){
for (int i=0;i<4;i++)
swap(f,f[imin(f,i)]);
}
int imin(int *f, int beg){
int m=f[beg];
int im=beg;
for (int i=beg+1;i<4;i++)
if (f>=m){
m=f;
im=i;
}
return im;
}
ВОТ. Про memcpy забудьте пока. Да боже мой, неужели так важны мелочи??? Спасибо, конечно ,за попытку помочь, но я все же не понимаю, неужели же нет способов передачи КОПИИ массива!!! :confused: Мне вроде говорили что можно кк-то скастовать (const char **) - не знаю, как это использовать, может вы подскажете. То, что функция очистки тормозит - несомненно, это сказал :rolleyes: дебаг.
Цитата: FloyDos
... я все же не понимаю, неужели же нет способов передачи КОПИИ массива!!! :confused:
Не создавайте фантомов.
Если нужна копия массива - делайте копию и передавайте. В языке такое не предусмотрено, тем более ваша программа на языке С. Со всеми вытекающими...
Цитата: FloyDos
Мне вроде говорили что можно кк-то скастовать (const char **) - не знаю, как это использовать, может вы подскажете.
Вас обманули.
Цитата: FloyDos
То, что функция очистки тормозит - несомненно, это сказал :rolleyes: дебаг.
Относительно всей программы - она не тормозит. Хотя, конечно, если профилировку дебагером делать...
Спасибо. Что ж, раз не предусмотрено - жаль.
А тогда поставим вопрос по-другому:
функция
void f(char **);
может еще что-то вроде const char** использовать? а внутри функции снимать константность - это возможно? Просто тогда косяки с вызовом выходят - нельзя будет передать в качестве аргумента неконстантый массив. А после выхода из функции в этом случае в основной программе не окажется ИЗМЕНЕННЫЙ массив??
А тогда поставим вопрос по-другому:
функция
void f(char **);
может еще что-то вроде const char** использовать? а внутри функции снимать константность - это возможно? Просто тогда косяки с вызовом выходят - нельзя будет передать в качестве аргумента неконстантый массив. А после выхода из функции в этом случае в основной программе не окажется ИЗМЕНЕННЫЙ массив??
Цитата: FloyDos
void f(char **);
может еще что-то вроде const char** использовать? а внутри функции снимать константность - это возможно?
Снять константность можно в следующем виде:
Код:
f( const char* str )
{
char* bad = const_cast<char*>(str);
bad[2] = '\0';
...
}
{
char* bad = const_cast<char*>(str);
bad[2] = '\0';
...
}
Цитата: FloyDos
Просто тогда косяки с вызовом выходят - нельзя будет передать в качестве аргумента неконстантый массив. А после выхода из функции в этом случае в основной программе не окажется ИЗМЕНЕННЫЙ массив??
Кхе... Это как?
P.S. Код обрамляют тегами [сode] и [/сode]
Благодарю за совет. А насчет const char ** - в этом случае нельзя передавать неконст массив.ошибка - не может конверт char** в const char**
Код:
void ff(const char **);
int _tmain(int argc, _TCHAR* argv[])
{
char k='A';
char **t0=new char *[2];
for (int i=0;i<2;i++){
t0=new char [4];
}
strcpy(t0[0],"abc");
strcpy(t0[1],"def");
ff(t0); //здесь ошибка выходит(
cout<<t0[0];
return 0;
}
void ff(const char **s){
char **b=const_cast<char**>(s);
b[0][0]='1';
}
int _tmain(int argc, _TCHAR* argv[])
{
char k='A';
char **t0=new char *[2];
for (int i=0;i<2;i++){
t0=new char [4];
}
strcpy(t0[0],"abc");
strcpy(t0[1],"def");
ff(t0); //здесь ошибка выходит(
cout<<t0[0];
return 0;
}
void ff(const char **s){
char **b=const_cast<char**>(s);
b[0][0]='1';
}
Цитата: FloyDos
Код:
...
ff((const char**)t0); //здесь ошибка выходит(
...
ff((const char**)t0); //здесь ошибка выходит(
...
А так?
Но согласен с предыдущим оратором - зачем все эти манипуляции? Создание неконстантного массива; передача его в функцию как константный; рекастинг обратно в неконстантный?
Вы слабо понимаете работу с массивами, указателями, ссылками? Гугл в помощь, да и ebook-и разные, ну сами знаете...
Согласна, теперь убедилась, что это операции бесполезные. И функция как изменяла массив, так и продолжает его изменять. что ж, воз и ныне там.
Благодарю еще раз за подсказку насчет const_char - по кр мере знаю теперь как это работает)) Жаль, что не помогло нисколько :D
Благодарю еще раз за подсказку насчет const_char - по кр мере знаю теперь как это работает)) Жаль, что не помогло нисколько :D
Цитата: FloyDos
Согласна, теперь убедилась, что это операции бесполезные. И функция как изменяла массив, так и продолжает его изменять. что ж, воз и ныне там.
Послушайте.
Вы передаете функции указатель на массив. Т.е. массив в памяти один, а при помощи этого указателя вы взаимодействуете с массивом.
Указателей на этот массив может быть сколько угодно, и через каждый из них вы общаетесь только с этим массивом! При копировании указателя или создании еще одного - массив не дублируется\не копируется\не переносится. Что здесь непонятного?
Цитата: FloyDos
Благодарю еще раз за подсказку насчет const_char - по кр мере знаю теперь как это работает))
Поверьте, пока не разберетесь с работой указателей и прочего перечисленного мною в предыдущем посте, вы ничего не знаете.
Цитата: FloyDos
Жаль, что не помогло нисколько :D
И не должно было. Пока вы не поймете, что именно вы хотите сделать с массивом.
я понимаю, что передаю функции УКАЗАТЕЛЬ на массив. Поэтому и вопрос возник, можно ли не указатель передавать в функцию, а копию массива.
По типу переменной - мы же можем передавать ее копию в функцию. Что ж, раз нельзя, будем искать другие выходы.
По типу переменной - мы же можем передавать ее копию в функцию. Что ж, раз нельзя, будем искать другие выходы.
Цитата: FloyDos
Что ж, раз нельзя, будем искать другие выходы.
Да не надо их искать, они известные (для вашего требования).
1. Сделать копию массива, и передавать функции указатель на эту копию.
2. Использовать какой-нить контейнер из, например, STL. Почитайте.
И третий вариант (самый правильный): пересмотреть логику работы программы. Поверьте, она ужасна.
Цитата: Lerkin
И третий вариант (самый правильный): пересмотреть логику работы программы. Поверьте, она ужасна.
ИМХО такое можно утверждать, лишь предложив альтернативный алгоритм.
согласна, вероятно есть и другие выходы. Я их не вижу, именно поэтому обратилась на форум.
Цитата: Lerkin
2. Использовать какой-нить контейнер из, например, STL. Почитайте.
Благодарю за совет, почитаем=)
Цитата: FloyDos
ИМХО такое можно утверждать, лишь предложив альтернативный алгоритм.
Их есть у меня. Предложения суммы - в приват. ;)
насмешили. Перефразируя госодина Линуса, алгоритмы должны быть бесплатными:cool:
Цитата: FloyDos
насмешили. Перефразируя госодина Линуса, алгоритмы должны быть бесплатными:cool:
Перефразируя другого господина:
Не продаётся вдохновение -
Но можно алгоритм продать.
Вы танки писать не пробовали?
Сударь, вы назвали логику кода ужасной - потрудитесь объясниться. А то уж слишком напоминает любимое всеми порицание мастдая;)
Сударь, вы назвали логику кода ужасной - потрудитесь объясниться. А то уж слишком напоминает любимое всеми порицание мастдая;)
а мне вот задачка понравилась. Решил толкануть идею бесплатно.
у меня подход вышел такой
1)нахажу воду которая вытечет (а раз может вытеч, то и втекти тоже сможет)
в результате в p1 имеем сколько воды вытечет, а воду которая затечет находим также как и ту что вытечет только проверяем на возможность распространяться во все стороны.
Мне интересно услышать какой подход был у автора(код посмотрел, за пару минт последовательность действий недопонял, а вдумываться лениво).
у меня подход вышел такой
1)нахажу воду которая вытечет (а раз может вытеч, то и втекти тоже сможет)
Код:
[COLOR="Blue"]var[/COLOR] cube,h,w; [COLOR="SandyBrown"]//входящие данные[/COLOR]
[COLOR="Blue"]var[/COLOR] cube1 = clone(cube);[COLOR="SandyBrown"]//куб заполняющийся водой[/COLOR]
[COLOR="Blue"]var[/COLOR] water = array(w*h);[COLOR="SandyBrown"]//координаты точек с водой[/COLOR]
[COLOR="Blue"]var[/COLOR] p1=0;
[COLOR="SandyBrown"]//пробегаем по нижней полосе и если там не кирпич, то там вода[/COLOR]
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[0]!='X')
{
cube1[0]='~';
water[p1]=point(0,i);
p1++;
}
}
[COLOR="SandyBrown"]//для воды в каждой клетке, смотрим есть ли ей возможность распространяться вверх или вбок[/COLOR]
i=0;
[COLOR="Blue"]while[/COLOR](i<p1)
{
x=water[p1].x;
y=water[p1].y;[COLOR="SandyBrown"]//здесь вода[/COLOR]
[COLOR="Blue"]if[/COLOR](cube1[x-1][y]='.')[COLOR="SandyBrown"]//а если здесь пусто то и тут она будет[/COLOR]
{
cube1[x-1][y]='~';
water[p1]=point(x-1,y);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x+1][y]='.')
{
cube1[x+1][y]='~';
water[p1]=point(x+1,y);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x-1][y+1]='.')
{
cube1[x-1][y+1]='~';
water[p1]=point(x-1,y+1);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x][y+1]='.')
{
cube1[x][y+1]='~';
water[p1]=point(x,y+1);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x+1][y+1]='.')
{
cube1[x+1][y+1]='~';
water[p1]=point(x+1,y+1);
p1++;
}
i++;
}
[COLOR="Blue"]var[/COLOR] cube1 = clone(cube);[COLOR="SandyBrown"]//куб заполняющийся водой[/COLOR]
[COLOR="Blue"]var[/COLOR] water = array(w*h);[COLOR="SandyBrown"]//координаты точек с водой[/COLOR]
[COLOR="Blue"]var[/COLOR] p1=0;
[COLOR="SandyBrown"]//пробегаем по нижней полосе и если там не кирпич, то там вода[/COLOR]
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[0]!='X')
{
cube1[0]='~';
water[p1]=point(0,i);
p1++;
}
}
[COLOR="SandyBrown"]//для воды в каждой клетке, смотрим есть ли ей возможность распространяться вверх или вбок[/COLOR]
i=0;
[COLOR="Blue"]while[/COLOR](i<p1)
{
x=water[p1].x;
y=water[p1].y;[COLOR="SandyBrown"]//здесь вода[/COLOR]
[COLOR="Blue"]if[/COLOR](cube1[x-1][y]='.')[COLOR="SandyBrown"]//а если здесь пусто то и тут она будет[/COLOR]
{
cube1[x-1][y]='~';
water[p1]=point(x-1,y);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x+1][y]='.')
{
cube1[x+1][y]='~';
water[p1]=point(x+1,y);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x-1][y+1]='.')
{
cube1[x-1][y+1]='~';
water[p1]=point(x-1,y+1);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x][y+1]='.')
{
cube1[x][y+1]='~';
water[p1]=point(x,y+1);
p1++;
}
[COLOR="Blue"]if[/COLOR](cube1[x+1][y+1]='.')
{
cube1[x+1][y+1]='~';
water[p1]=point(x+1,y+1);
p1++;
}
i++;
}
в результате в p1 имеем сколько воды вытечет, а воду которая затечет находим также как и ту что вытечет только проверяем на возможность распространяться во все стороны.
Мне интересно услышать какой подход был у автора(код посмотрел, за пару минт последовательность действий недопонял, а вдумываться лениво).
оО здорово приятно видеть заинтересованных людей.
Мой алгоритм:
[FONT="Book Antiqua"]Мелкие подробности:[/FONT]
для реализации именно четырех способов завела массив
что существенно упростило код в функции основной обработки:
(Это из функции putinnext - условие перемещения выливаемой воды в соседнюю ячейку проверяется в зависимости от способа вытаскивания - где b[res]==true, там условие и является определяющим для рекурсии)
res - от 1 до 4 - передается в функцию при вызове, обозначает номер способа (последовательность выбрана условно)
Будут уточняющие вопросы - задавайте, отвечу с радостью. Может, так и более рац. решение всплывет ;)
Мой алгоритм:
Цитата:
Когда структуру погружают в воду, вода заполняет всё свободное пространство внутри структуры, которое она может заполнить.
1)заполняем все, что доступно из дырок, водой
Код:
void paintwithwater(char **col,int x,int y){
if (col[x][y]=='.')
col[x][y]=water;
for (int i=0;i<8;i++)
if (col[x+a[0]][y+a[1]]=='.')
paintwithwater(col, x+a[0],y+a[1]);
}
if (col[x][y]=='.')
col[x][y]=water;
for (int i=0;i<8;i++)
if (col[x+a[0]][y+a[1]]=='.')
paintwithwater(col, x+a[0],y+a[1]);
}
Цитата:
Возможны 4 способа погружения (и вытаскивания). При этом боковые плексигласовые грани всегда вертикальны).
2)для каждого из четырех способов вытаскивания: для каждой клетки с водой пытаемся ее "вылить" - "перемещаем ее по смежным клеткам", причем условие перемещения такое: высота клетки, которую обрабатываемая проходит, не должна быть выше чем высота самой обрабатываемой.
Код:
void putinnext(char **col, int x0, int y0, int x, int y, int res){
bool ff[4];
if (col[x][y]==hole) //если достигли дыры, то помечаем выливаемую кк away
col[x0][y0]=away;
else{
col[x][y]=done;
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
}
}//x0, y0 - координаты "выливаемой" клетки
//x, y- координаты текущей клетки, через которую проводим "выливаемую"
bool ff[4];
if (col[x][y]==hole) //если достигли дыры, то помечаем выливаемую кк away
col[x0][y0]=away;
else{
col[x][y]=done;
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
}
}//x0, y0 - координаты "выливаемой" клетки
//x, y- координаты текущей клетки, через которую проводим "выливаемую"
[FONT="Book Antiqua"]Мелкие подробности:[/FONT]
для реализации именно четырех способов завела массив
Код:
const bool b[4][4]={
{1,0,0,0},
{0,1,0,0},
{0,0,1,0},
{0,0,0,1}
};
{1,0,0,0},
{0,1,0,0},
{0,0,1,0},
{0,0,0,1}
};
что существенно упростило код в функции основной обработки:
Код:
for (int i=0;i<8;i++){
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
ff[0]=(x+a[0]>=x0)&&b[res][0];
ff[1]=(y+a[1]>=y0)&&b[res][1];
ff[2]=(x+a[0]<=x0)&&b[res][2];
ff[3]=(y+a[1]<=y0)&&b[res][3];
if (
(
(col[x+a[0]][(y+a[1])]==water)
||
(col[x+a[0]][(y+a[1])]==hole)
)
&&
(ff[0]||ff[1]||ff[2]||ff[3])
)
putinnext(col,x0,y0,x+a[0],y+a[1],res);
}
(Это из функции putinnext - условие перемещения выливаемой воды в соседнюю ячейку проверяется в зависимости от способа вытаскивания - где b[res]==true, там условие и является определяющим для рекурсии)
res - от 1 до 4 - передается в функцию при вызове, обозначает номер способа (последовательность выбрана условно)
Будут уточняющие вопросы - задавайте, отвечу с радостью. Может, так и более рац. решение всплывет ;)
Цитата: max_br
воду которая затечет находим также как и ту что вытечет только проверяем на возможность распространяться во все стороны.
В этом вы правы: затекающая вода распространяется во всех направлениях.Браво!
Но не учли при выливании воды закон сообщающихся сосудов, или, как сказано в условии задачи:
Цитата:
Кроме того, из-за гидростатического давления уровень воды во всех оставшихся внутри конструкции «лужах» не может быть выше, чем дно самой нижней дырки, через которую вода может вытекать.
А у вас:
Цитата:
для воды в каждой клетке, смотрим есть ли ей возможность распространяться вверх или вбок
Поняли, в чем недочет?Вопрос должен стоять не в направлении, а в уровне.
Цитата: FloyDos
Вы танки писать не пробовали?
Платите? Напишем...
Цитата: FloyDos
Сударь, вы назвали логику кода ужасной - потрудитесь объясниться.
Легко, сударыня. Подобное задание я использую в своей организации - как один из квалификационных тестов. Можно сказать, что вы его провалили.
Цитата: FloyDos
А то уж слишком напоминает любимое всеми порицание мастдая;)
К чему такое некислое сравнение? Вы имеете какое-либо отношение к разработке Windows?
Хотя тема ушла в несколько другом направлении, хочу вернуться к проблеме, которой тема была посвящена. По поводу предложенного первого варианта (создать копию массива и ее передавать в функцию). Как вариант создания копии массива вполне можно использовать ф-ию memcpy, о которой можно прочитать здесь.
Цитата: FloyDos
Кроме того, замечено, что с использованием memcpy и memmove образец, с к-рого делалась копия, тоже изменяется с изменением копии.
Не скажете - вы это сами заметили, или это с чужих слов? Откуда столь плохое мнение о memcpy, например? :)
memcpy для копирования массива использовать можно, и если все правильно сделать, то копия будет полностью независима от оригинала, и изменение копии не вызовет никаких изменений в оригинале. Только при копировании через memcpy, ИМХО, без reinterpret_cast не обойтись. Если надо - могу накидать небольшой пример на неск. строчек, как это можно сделать.
Цитата: Ghox
...
memcpy для копирования массива использовать можно, и если все правильно сделать, то копия будет полностью независима от оригинала, и изменение копии не вызовет никаких изменений в оригинале.
memcpy для копирования массива использовать можно, и если все правильно сделать, то копия будет полностью независима от оригинала, и изменение копии не вызовет никаких изменений в оригинале.
Объясните мне, лошку последнему, что можно сделать неправильно при использовании memcpy? Единственное, что могу придумать, так это вариант с копированием массива A в массив B, и продолжением (по невнимательности) работы с указателем на массив A. Еще варианты можно какие-нить разумные предположить? Перекрытие массивов?
Цитата: Lerkin
Объясните мне, лошку последнему, что можно сделать неправильно при использовании memcpy? Единственное, что могу придумать, так это вариант с копированием массива A в массив B, и продолжением (по невнимательности) работы с указателем на массив A. Еще варианты можно какие-нить разумные предположить? Перекрытие массивов?
Ага;)
Цитата: Lerkin
Объясните мне, лошку последнему, что можно сделать неправильно при использовании memcpy?
При незнании (а вы сами обнаружили у автора темы пробелы в знании работы с указателями) и / или с кривыми руками неправильно можно сделать много чего. А в контексте данной задачи (создание копии массива, т.к. memcpy можно использовать не только для копирования массивов) - например, можно по ошибке установить указатель на начало результата копирования в область памяти, занимаемую источником копирования (в середину или на начало). Или неправильно задать число символов, которые должны быть скопированы. Ситуация, когда новичок, слабо разбирающийся в указателях, делает такую ошибку - вполне возможна, ИМХО.
Например, вот такое:
Код:
int main() {
int mas[4] = {1, 2, 3, 4};
char * src = (char*)&mas[0];
// новичок наивно полагает
// что достаточно сместить указатель char на 4 позиции
// и там будет свободная область памяти
// которую можно использовать для массива-копии:
char * dest = src + 4;
memcpy(dest, src, 4);
int * copy_mas = (int*)dest;
// ну и далее пытается юзать copy_mas:
copy_mas[0] += 10;
}
int mas[4] = {1, 2, 3, 4};
char * src = (char*)&mas[0];
// новичок наивно полагает
// что достаточно сместить указатель char на 4 позиции
// и там будет свободная область памяти
// которую можно использовать для массива-копии:
char * dest = src + 4;
memcpy(dest, src, 4);
int * copy_mas = (int*)dest;
// ну и далее пытается юзать copy_mas:
copy_mas[0] += 10;
}
Вот как вы думаете - такое невозможно в коде начинающего? Правда, сам я такую ошибку не делал.
Пример, кстати, вполне компилирующийся и даже как-то работает...
Цитата: Lerkin
Единственное, что могу придумать, так это вариант с копированием массива A в массив B, и продолжением (по невнимательности) работы с указателем на массив A.
Ну или это.
Цитата: Lerkin
Еще варианты можно какие-нить разумные предположить? Перекрытие массивов?
Да, и перекрытие (впрочем это ИМХО тот вариант о котором я в этом посте выше написал).
А вообще я думаю надо подождать что автор темы ответит. Ведь у нее же (вроде как) что-то не получилось с memcpy. Ее кстати просили привести пример кода, в котором она пробовала копировать с помощью memcpy. Но пример она не привела, так что, возможно, она решила, что то, что memcpy нельзя в данной задаче использовать, с чужих слов.
ЗЫ. Обидеть никого ничем не хотел. :)
Цитата: Ghox
Только при копировании через memcpy, ИМХО, без reinterpret_cast не обойтись.
А зачем там reinterpret_cast?
Цитата: nikitozz
А зачем там reinterpret_cast?
Хмм... можно и чем-то вроде (char*)&a[0] или даже (char*)a обойтись, так что я ошибся...
Хотя если необходимо использовать какой-то cast (если используется практика программирования, когда все преобразования типов делаются исключительно через cast-ы, чтобы легче было искать места в коде где этим преобразования производятся), то я думаю, что reinterpret_cast - единственный который можно здесь использовать. Знатоки пусть меня поправят, если я не прав...
про сообщающиеся сосуды я действительно неподумал.
а если так:
будем затапливать постепенно
шаг n
x.x..
x..x~
xxxx~
шаг n+1
x~x~~
x~~x~
xxxx~
когда будем вытаскивать выливаться будет только та вода которая на каждом шаге добовлялась в верхний рядок шага.
а если так:
будем затапливать постепенно
шаг n
x.x..
x..x~
xxxx~
шаг n+1
x~x~~
x~~x~
xxxx~
когда будем вытаскивать выливаться будет только та вода которая на каждом шаге добовлялась в верхний рядок шага.
Код:
[COLOR="SandyBrown"]//в первом все пустые с водой[/COLOR]
total=0;[COLOR="SandyBrown"]//всего воды наберется[/COLOR]
out=0;[COLOR="SandyBrown"]//вода которая вытечет[/COLOR]
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[0]=='.')
{
cube[0]='~';
total++;
out++;
}
}
[COLOR="Blue"]for[/COLOR](n=1;n<h;n++)
{
[COLOR="SandyBrown"]//подымаем воду на шаг[/COLOR]
p1=0;
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[n-1]=='~')
{
[COLOR="Blue"]for[/COLOR](j=-1;j<=1;j++;)
{
[COLOR="Blue"]if[/COLOR]((i+j>=0)&&(i+j<w)&&(cube[i+j][n]=='.'))
{
cube[i+j][n]='~'
water[p1]=point(i+j,n);
p1++;
total++;
}
}
}
}
[COLOR="SandyBrown"]//смотрим куда в результате этого шага вода может затечь[/COLOR]
i=0;
[COLOR="Blue"]while[/COLOR](i<p1)
{
x=water.x;
y=water.y;//здесь вода
[COLOR="Blue"]for[/COLOR](j=-1;j<=1;j++;)for(k=-1;k<=1;k++;)
{
[COLOR="Blue"]if[/COLOR]((x+j>=0)&&(x+j<w)&&(y+k>=0)&&(y+k<=n)&&(cube[x+j][y+k]=='.'))
{
cube[x+j][y+k]='~'
water[p1]=point(x+j,y+k);
p1++;
total++;
}
}
i++
}
[COLOR="SandyBrown"]//считаем ту воду которая выльется[/COLOR]
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[n]=='~')
{
out++;
}
}
}
total=0;[COLOR="SandyBrown"]//всего воды наберется[/COLOR]
out=0;[COLOR="SandyBrown"]//вода которая вытечет[/COLOR]
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[0]=='.')
{
cube[0]='~';
total++;
out++;
}
}
[COLOR="Blue"]for[/COLOR](n=1;n<h;n++)
{
[COLOR="SandyBrown"]//подымаем воду на шаг[/COLOR]
p1=0;
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[n-1]=='~')
{
[COLOR="Blue"]for[/COLOR](j=-1;j<=1;j++;)
{
[COLOR="Blue"]if[/COLOR]((i+j>=0)&&(i+j<w)&&(cube[i+j][n]=='.'))
{
cube[i+j][n]='~'
water[p1]=point(i+j,n);
p1++;
total++;
}
}
}
}
[COLOR="SandyBrown"]//смотрим куда в результате этого шага вода может затечь[/COLOR]
i=0;
[COLOR="Blue"]while[/COLOR](i<p1)
{
x=water.x;
y=water.y;//здесь вода
[COLOR="Blue"]for[/COLOR](j=-1;j<=1;j++;)for(k=-1;k<=1;k++;)
{
[COLOR="Blue"]if[/COLOR]((x+j>=0)&&(x+j<w)&&(y+k>=0)&&(y+k<=n)&&(cube[x+j][y+k]=='.'))
{
cube[x+j][y+k]='~'
water[p1]=point(x+j,y+k);
p1++;
total++;
}
}
i++
}
[COLOR="SandyBrown"]//считаем ту воду которая выльется[/COLOR]
[COLOR="Blue"]for[/COLOR](i=0;i<w;i++)
{
[COLOR="Blue"]if[/COLOR](cube[n]=='~')
{
out++;
}
}
}
http://rapidshare.com/files/267749910/D-water.rar.html
Тут можете скачать тестирующую систему для данной задачи и набор тестов. просто запускаете батник и смотрите результат (думаю, разберетесь, название вашего экзешника должно совпадать с установками батника)
Тут можете скачать тестирующую систему для данной задачи и набор тестов. просто запускаете батник и смотрите результат (думаю, разберетесь, название вашего экзешника должно совпадать с установками батника)