Ĺadny brzuch
witam
mam tablice zer i jedynek taka jak poniżej (przykładowo)
000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000111100 000011000000000000001100000000011000000000010110 000001100000000000011000000000011000000000000000 000000110000000000110000000000011000000000000000 100000011000000001100000000000011000000000000000 000000000110000011000000000000011000000000000000 000000000011000110000000000000011000000000000000 000100000001101100000000001100011000000000000000 000100000000111000000000000100011111111110000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000
teraz chodzi mi o to aby wyznaczyć te obszary, w których są grupy jedynek, tak jak na załączonej fotce poniżej
http://img204.images...01010101ba3.png
teraz mam pytanie, jakim sposobem znaleźć lewy górny i prawy dolny róg tych obszarów aby to wyszukiwanie szło w miarę szybko bo bede używał bardzo dużych tablic
moim zdaniem to chyba rekurencyjnie to musisz zrobic, ze gdy najedziesz na jakas jedynke to bedziesz przechodzil do nastpenej od razu (sprawdzasz warunek gora, dol, prawo, lewo ), zliaczajac przy tym min, max wymiarow tego obszaru..
jak wiadomo rekurencja jest wolniejsza od rozwiazan iteracyjnych, ale wymyslic kod iteracyjny do tego to sie mozna narobic ;)
ja sie tego nie podejme ;)
a jakie bedziesz mial max wymiary macierzy??
Użytkownik fernandez edytował ten post 23 kwiecień 2007, 10:49
Pewnie jest juz na to jakis algo, a gdyby zrobic w taki sposob, ze szukasz jedynki, jak juz ja znajdziesz to poczynajac od niej szukasz kolejne przylegajace do niej, zapisujac te z minimalnymi i max wartosciami (x,y) [zeby wyszedl gorny lewy i dolny prawy rog "obszaru"], po zakonczeniu (jezeli juz zadna jedynka nie przylega do pozostalych) wymazujesz (ustawiasz na 0) sobie te ktore wlasnie brales pod uwage i szukasz nastepnej 1 w macierzy
tez właśnie myślałem nad rekurencja. jak znajdę 1 to badam jego "sąsiedztwo" i wszystkie z nim przyległe zamieniam na 2. potem szukam najbardziej wychylonych dwójek i w ten sposób ustalam skrajne narożniki. na koniec zeruje ten obszar i szukam dalej
dokładnie to będzie tak że będę wczytywał grafikę z tekstem, po czym "progował" obraz do wartości 0 i 1, następnie muszę znaleźć te obszary ze znakami. właściwie wstępnie mógłbym sprawdzić w których wierszach nie ma czarnych piksli (przerwy między tekstami wersami tekstu) i tylko rekurencyjnie wyszukiwać w tych w których na pewno są.
właśnie chciałbym sie zapytać jak najszybciej to zrobić, bo czasem tablica będzie miała około 2000x1000 a może nawet większe
rekurencja tu nie jest potrzebna, przeciez to co napisalem mozna zrobic bez problemu iteracyjnie.
rekurencja tu nie jest potrzebna, przeciez to co napisalem mozna zrobic bez problemu iteracyjnie.
znalezienie jedynki mozna zrobic iteracyjnie ale jak potem poszukac sąsiednich jedynek. wydaje mi sie ze tu trzeba uzyć podobnego algorytmu do przeszukiwania grafów w głab lub w szerz a to sa metody rekurencyjne. jak to mozna zrobić iteracyjnie, te sąsiednie jedynki? bo nie wiem
oczywiscie ze sie to da zrobic iteracyjnie, ale robilem podobny program, tylko mial on zliczac ile pol (w tym przypadku "1") jest w danym obszarze (obszar to wszystki "1" polaczone ze soba bezposrednio)
i ja pisalem rekurencyjnie co zajelo pare linijek, a kolego pisal iteracyjnie i program mu sie strasznie rozrosla i tak nie dzialal dla kazdego przypadku :/
tutaj problem jest podobny..
oto kod:
//biale = 1, czarne = 0 (albo odwrotnie, ale tutaj jest to niewazne), ile - ilosc pol, matx to wiadomo;) void odwiedz( short int matx[ MAX ][ MAX ], short int xx, short int yy, short int *ile ) { matx[ xx ][ yy ] = BIALE; (*ile)++; if( matx[ xx - 1 ][ yy ] == CZARNE ) { odwiedz( matx, xx - 1, yy, &(*ile) ); } if( matx[ xx + 1 ][ yy ] == CZARNE ) { odwiedz( matx, xx + 1, yy, &(*ile) ); } if( matx[ xx ][ yy - 1 ] == CZARNE ) { odwiedz( matx, xx, yy - 1, &(*ile) ); } if( matx[ xx ][ yy + 1 ] == CZARNE ) { odwiedz( matx, xx, yy + 1, &(*ile) ); } }
zostalo to puszczone w petli od poczatku do konca macierzy, a odwiedz() bylo uruchamiane przy warunku gdy napotkalo na CZARNE..
kod pisany podczas moich pierwszych krokow z C, wiec rozwiazanie moze troche dziwic , ale dziala ;)
troche to przerobisz pod sowje potrzeby i bedzie oki, a dla macierzy nawet 2000x2000 nie powinno to dzialac za wolno
dzięki fernandez, po kilku przeróbkach działa.
przy tablicy 2000x3100 i około 10-15% zapełnieniu jedynkami wyszukiwanie trwa około 15sek (około 2000 obszarów). z tym że chciałbym teraz troszkę zoptymalizować kod, mianowicie narożniki zapisuje w tablicy statycznej [3000][4]. i tu mam kolejne pytanie czy da sie aż cztery elementy zapisać w jednym "węźle" listy z biblioteki STL, jak tak to jak?
nie wiem dokladnie co chcesz zrobic,..
ale przypomnialo mi sie jeszcze jedno, moze sie przydac ;)
otoz zeby nie robic jakis niepotrzenych warunkow, do tabliy MxN dodaje 2 wymiar na "obramowanie", czyli M+2xN+2..
i dla M=0 lub M=M-1 oraz dla N=0 lub N=N-1 wypelniam tablice zerami (w moim przypadku BIALE)
mysle ze to troszke zaoszczedzi czasu..
dokładnie chodzi mi o coś takiego
struct ramka{ int LewyGornyX; int LewyGornyY; int PrawyDolnyX; int PrawyDolnyY; };
i czy da zrobić listę takich struktur, czy lepiej te narozniki wpisywać w liste w jakimś porządku i wtedy bedzie 4 razy dłuższa. chodzi mi o to aby nie przekroczyć tego wymiaru tablicy z tymi narożnikami, jeśli obszarów będzie więcej niż 3000
chodzi Ci ze chcesz pamietac znaleziony obszar tak??
mozesz "wrzucac" dane (tak jak napisales) w strukture (lub po prostu w tablice 4-elementowa int) i kazdorazwo dodawac do kontenera (bardzo wygodne narzedzie)
edit:
@down
wole sie upewnic..
Użytkownik fernandez edytował ten post 26 kwiecień 2007, 02:11
chodzi Ci ze chcesz pamietac znaleziony obszar tak??
mozesz "wrzucac" dane (tak jak napisales) w strukture (lub po prostu w tablice 4-elementowa int) i kazdorazwo dodawac do kontenera (bardzo wygodne narzedzie)
przeciez on wlasnie pytal czy tak moze :> tylko pytal o liste. mozesz uzyc listy albo vectora zaleznie co pozniej bedziesz chcial z tym zrobic.
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
mam tablice zer i jedynek taka jak poniżej (przykładowo)
000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000111100 000011000000000000001100000000011000000000010110 000001100000000000011000000000011000000000000000 000000110000000000110000000000011000000000000000 100000011000000001100000000000011000000000000000 000000000110000011000000000000011000000000000000 000000000011000110000000000000011000000000000000 000100000001101100000000001100011000000000000000 000100000000111000000000000100011111111110000000 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000
teraz chodzi mi o to aby wyznaczyć te obszary, w których są grupy jedynek, tak jak na załączonej fotce poniżej
http://img204.images...01010101ba3.png
teraz mam pytanie, jakim sposobem znaleźć lewy górny i prawy dolny róg tych obszarów aby to wyszukiwanie szło w miarę szybko bo bede używał bardzo dużych tablic
moim zdaniem to chyba rekurencyjnie to musisz zrobic, ze gdy najedziesz na jakas jedynke to bedziesz przechodzil do nastpenej od razu (sprawdzasz warunek gora, dol, prawo, lewo ), zliaczajac przy tym min, max wymiarow tego obszaru..
jak wiadomo rekurencja jest wolniejsza od rozwiazan iteracyjnych, ale wymyslic kod iteracyjny do tego to sie mozna narobic ;)
ja sie tego nie podejme ;)
a jakie bedziesz mial max wymiary macierzy??
Użytkownik fernandez edytował ten post 23 kwiecień 2007, 10:49
Pewnie jest juz na to jakis algo, a gdyby zrobic w taki sposob, ze szukasz jedynki, jak juz ja znajdziesz to poczynajac od niej szukasz kolejne przylegajace do niej, zapisujac te z minimalnymi i max wartosciami (x,y) [zeby wyszedl gorny lewy i dolny prawy rog "obszaru"], po zakonczeniu (jezeli juz zadna jedynka nie przylega do pozostalych) wymazujesz (ustawiasz na 0) sobie te ktore wlasnie brales pod uwage i szukasz nastepnej 1 w macierzy
tez właśnie myślałem nad rekurencja. jak znajdę 1 to badam jego "sąsiedztwo" i wszystkie z nim przyległe zamieniam na 2. potem szukam najbardziej wychylonych dwójek i w ten sposób ustalam skrajne narożniki. na koniec zeruje ten obszar i szukam dalej
dokładnie to będzie tak że będę wczytywał grafikę z tekstem, po czym "progował" obraz do wartości 0 i 1, następnie muszę znaleźć te obszary ze znakami. właściwie wstępnie mógłbym sprawdzić w których wierszach nie ma czarnych piksli (przerwy między tekstami wersami tekstu) i tylko rekurencyjnie wyszukiwać w tych w których na pewno są.
właśnie chciałbym sie zapytać jak najszybciej to zrobić, bo czasem tablica będzie miała około 2000x1000 a może nawet większe
rekurencja tu nie jest potrzebna, przeciez to co napisalem mozna zrobic bez problemu iteracyjnie.
rekurencja tu nie jest potrzebna, przeciez to co napisalem mozna zrobic bez problemu iteracyjnie.
znalezienie jedynki mozna zrobic iteracyjnie ale jak potem poszukac sąsiednich jedynek. wydaje mi sie ze tu trzeba uzyć podobnego algorytmu do przeszukiwania grafów w głab lub w szerz a to sa metody rekurencyjne. jak to mozna zrobić iteracyjnie, te sąsiednie jedynki? bo nie wiem
oczywiscie ze sie to da zrobic iteracyjnie, ale robilem podobny program, tylko mial on zliczac ile pol (w tym przypadku "1") jest w danym obszarze (obszar to wszystki "1" polaczone ze soba bezposrednio)
i ja pisalem rekurencyjnie co zajelo pare linijek, a kolego pisal iteracyjnie i program mu sie strasznie rozrosla i tak nie dzialal dla kazdego przypadku :/
tutaj problem jest podobny..
oto kod:
//biale = 1, czarne = 0 (albo odwrotnie, ale tutaj jest to niewazne), ile - ilosc pol, matx to wiadomo;) void odwiedz( short int matx[ MAX ][ MAX ], short int xx, short int yy, short int *ile ) { matx[ xx ][ yy ] = BIALE; (*ile)++; if( matx[ xx - 1 ][ yy ] == CZARNE ) { odwiedz( matx, xx - 1, yy, &(*ile) ); } if( matx[ xx + 1 ][ yy ] == CZARNE ) { odwiedz( matx, xx + 1, yy, &(*ile) ); } if( matx[ xx ][ yy - 1 ] == CZARNE ) { odwiedz( matx, xx, yy - 1, &(*ile) ); } if( matx[ xx ][ yy + 1 ] == CZARNE ) { odwiedz( matx, xx, yy + 1, &(*ile) ); } }
zostalo to puszczone w petli od poczatku do konca macierzy, a odwiedz() bylo uruchamiane przy warunku gdy napotkalo na CZARNE..
kod pisany podczas moich pierwszych krokow z C, wiec rozwiazanie moze troche dziwic , ale dziala ;)
troche to przerobisz pod sowje potrzeby i bedzie oki, a dla macierzy nawet 2000x2000 nie powinno to dzialac za wolno
dzięki fernandez, po kilku przeróbkach działa.
przy tablicy 2000x3100 i około 10-15% zapełnieniu jedynkami wyszukiwanie trwa około 15sek (około 2000 obszarów). z tym że chciałbym teraz troszkę zoptymalizować kod, mianowicie narożniki zapisuje w tablicy statycznej [3000][4]. i tu mam kolejne pytanie czy da sie aż cztery elementy zapisać w jednym "węźle" listy z biblioteki STL, jak tak to jak?
nie wiem dokladnie co chcesz zrobic,..
ale przypomnialo mi sie jeszcze jedno, moze sie przydac ;)
otoz zeby nie robic jakis niepotrzenych warunkow, do tabliy MxN dodaje 2 wymiar na "obramowanie", czyli M+2xN+2..
i dla M=0 lub M=M-1 oraz dla N=0 lub N=N-1 wypelniam tablice zerami (w moim przypadku BIALE)
mysle ze to troszke zaoszczedzi czasu..
dokładnie chodzi mi o coś takiego
struct ramka{ int LewyGornyX; int LewyGornyY; int PrawyDolnyX; int PrawyDolnyY; };
i czy da zrobić listę takich struktur, czy lepiej te narozniki wpisywać w liste w jakimś porządku i wtedy bedzie 4 razy dłuższa. chodzi mi o to aby nie przekroczyć tego wymiaru tablicy z tymi narożnikami, jeśli obszarów będzie więcej niż 3000
chodzi Ci ze chcesz pamietac znaleziony obszar tak??
mozesz "wrzucac" dane (tak jak napisales) w strukture (lub po prostu w tablice 4-elementowa int) i kazdorazwo dodawac do kontenera (bardzo wygodne narzedzie)
edit:
@down
wole sie upewnic..
Użytkownik fernandez edytował ten post 26 kwiecień 2007, 02:11
chodzi Ci ze chcesz pamietac znaleziony obszar tak??
mozesz "wrzucac" dane (tak jak napisales) w strukture (lub po prostu w tablice 4-elementowa int) i kazdorazwo dodawac do kontenera (bardzo wygodne narzedzie)
przeciez on wlasnie pytal czy tak moze :> tylko pytal o liste. mozesz uzyc listy albo vectora zaleznie co pozniej bedziesz chcial z tym zrobic.