Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 49 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5
[Architektura niezależna] testy 
Autor Wiadomość
Gwiazda 2

Dołączył(a): 7 paź 2010, o 20:33
Posty: 43
Post Re: [Architektura niezależna] testy
Dla największego zestawu przechodziła właśnie rekurencja (mój pierwszy pomysł) - tj. wypełnienie kwadratu n*n dwójkami, tam gdzie był hash 1, i okolice jako "strażnicy" - 0. Czyli coś takiego:
Kod:

00000
02220
01120
01120
00000
 

Dla wzorku:
Kod:
...
##.
##.

I później po pierwszym wierszu, pierwszej kolumnie, ostatnim wierszu i ostatniej kolumnie, rekurencyjnie usuwało wszystkie 2 sąsiadujące z 0 - i za każdym usunięciem pole--; I przechodziło :(


Poprawka: Nawet jeśli jechaliśmy później po wszystkich ( nie tylko pierwszej i ostatniej) kolumnach i wierszch, też przechodziło. I to z niezłymi czasami :D


14 kwi 2011, o 10:28
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 10:02
Posty: 83
Post Re: [Architektura niezależna] testy
Mi się nie chciało myśleć więc puszczałam BFS-a od każdej kropki z ogrodzenia :)


14 kwi 2011, o 10:30
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 15 cze 2010, o 19:01
Posty: 11
Post Re: [Architektura niezależna] testy
W tym zadaniu to ja to chyba wymyśliłem wzorcówke bo zadanie zrobione dynamicznie i najgorszy czas to 29ms :)
I do tego zuzycie pamieci 884


14 kwi 2011, o 12:30
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 12 paź 2010, o 17:37
Posty: 4
Post Re: [Architektura niezależna] testy
Ja puściłem szukanie pierwszej kropki wewnątrz, a później rekurencyjnie zamiana kropek na #, potem zliczenie # i działa ;D
Myślałem o BFS ale wpadłem jak można było go zaaplikowawać. Byłbym wdzięczny gdybyś podała mi twój algorytm lub kod :D


14 kwi 2011, o 13:57
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 10:02
Posty: 83
Post Re: [Architektura niezależna] testy
bajorekp napisał(a):
Ja puściłem szukanie pierwszej kropki wewnątrz, a później rekurencyjnie zamiana kropek na #, potem zliczenie # i działa ;D
Myślałem o BFS ale wpadłem jak można było go zaaplikowawać. Byłbym wdzięczny gdybyś podała mi twój algorytm lub kod :D


Proszę bardzo mało elegancki:)
Kod:

#include<iostream>
#include<vector>
#include <deque>
using namespace std;
struct para{
    int x,y;
};
vector<para>brzeg;
deque<para>kolejka;
int main(){
  ios_base::sync_with_stdio(0);
  int rx[8]={1,-1,0,0,1,-1,1,-1};
  int ry[8]={0,0,1,-1,1,-1,-1,1};
  int tt,n;
    cin>>tt;
    while(tt--){
        int ile=0;
        cin>>n;
        brzeg.clear();
        kolejka.clear();
 
        para c;
        c.y=0;
        for(int i=0;i<n;i++){
            c.x=i;
            brzeg.push_back(c);
        }
        c.y=n-1;
        for(int i=0;i<n;i++){
            c.x=i;
            brzeg.push_back(c);
        }
        c.x=0;
        for(int i=1;i<n-1;i++){
            c.y=i;
            brzeg.push_back(c);
        }
        c.x=n-1;
        for(int i=1;i<n-1;i++){
            c.y=i;
            brzeg.push_back(c);
        }
 
        char t[n][n];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
              cin>>t[i][j];
        //bfs - po brzegu
        for(int i=0;i<brzeg.size();i++){
            if(t[brzeg[i].x][brzeg[i].y]=='.'){
                //<<"B: "<<x<<" "<<y<<"\n";
                kolejka.push_front(brzeg[i]);
                while(!kolejka.empty()){
                    para co=kolejka.back();
                    kolejka.pop_back();
                    ile++;
                    t[co.x][co.y]='#';
                    for(int j=0;j<8;j++){
                        para w;
                        w.x=co.x+rx[j];
                        w.y=co.y+ry[j];
                        if(w.x<0 || w.x>=n)
                          continue;
                        if(w.y<0 || w.y>=n)
continue;
                        if(t[w.x][w.y]=='.')
                            kolejka.push_front(w);
                            t[w.x][w.y]='#';
                    }
                }
            }
        }
        cout<<n*n-ile<<"\n";
    }
    return 0;
}


14 kwi 2011, o 14:00
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 25 lut 2010, o 20:19
Posty: 69
Post Re: [Architektura niezależna] testy
Ja robiłem inaczej. Przelatywałem sobie cały kwadracik i miałem zmienną bool licz, której wartość mówiła czy mamy do wyniku doliczać czy nie napotykane kropki. Więc tak - gdy aktualne pole to slash - sprawdzamy czy na polu [x-1][y] i [x+1][y] też są slashe, jeśli tak - odwracam wartość licz na przeciwną, jeśli nie - sprawdzam czy któreś z tych pól jest slashem, jeśli nie - mamy do czynienia z kilkoma slashami w jednej linii, jeśli tak to albo ta slashowa linia się zaczyna albo kończy, więc ustawiam sobie zmienne poczatek i koniec, które będą mi mówiły o tym czy początek/koniec danej linii sąsiadował ze slashem położonym nad/pod nim i tak np. dla slasha NAD zmienna ma wartość 1, dla POD - 2, a gdy nie została jeszcze ustalona po poprzedniej linii - 0. No i tym oto sposobem możemy wyznaczyć początki/końce "linii slashów", pozostaje tylko sprawdzać czy nad!=pod i jeśli jest to prawdą - zmienić zmienną licz na przeciwną. Oczywiście dla napotkanego slasha +1 do wyniku. Trochę dziwny sposób i równie dziwny kod, no ale poszło :P


14 kwi 2011, o 16:22
Zobacz profil
Gwiazda 2Gwiazda 2

Dołączył(a): 2 sie 2010, o 20:56
Posty: 27
Post Re: [Architektura niezależna] testy
Mój to dopiero jest nieelegancki ;).
Kod:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    int t,n,z,l,p,g,d;
    cin>>t;
    while(t--)
    {
        cin>>n;z=0;
        char b[n][n];
        for(int y=0;y<n;y++)
            for(int x=0;x<n;x++)
                cin>>b[x][y];
        for(int y=0;y<n;y++)
            for(int x=0;x<n;x++)
            {
                if((b[x-1][y]==' ' or b[x+1][y]==' ' or b[x][y-1]==' ' or b[x][y+1]==' ') and b[x][y]=='.')b[x][y]=' ';
                else if(b[x][y]=='#')z++;
                else if(b[x][y]!=' ' and (b[x-1][y]=='x' or b[x+1][y]=='x' or [x][y-1]=='x' or b[x][y+1]=='x')){b[x][y]='x';z++;}
                else if(b[x][y]!=' ' and x>0 and x<n-1 and y>0 and y<n-1)
                {
                    l=0;p=0;g=0;d=0;
                    for(int o=0;o<x;o++){if(b[o][y]=='#' and b[o-1][y]!='#')l++;}
                    for(int o=x+1;o<n;o++){if(b[o][y]=='#' and b[o+1][y]!='#')p++;}
                    for(int o=0;o<y;o++){if(b[x][o]=='#' and b[x][o+1]!='#')g++;}
                    for(int o=y+1;o<n;o++){if(b[x][o]=='#' and b[x][o-1]!='#')d++;}
                    if(l%2==1 and p%2==1  and g%2==1  and d%2==1){z++;b[x][y]='x';}
                }
                else if(b[x][y]!='#'){b[x][y]=' ';}
            }
        for(int y=n-1;y>=0;y--)
            for(int x=n-1;x>=0;x--)
            {
                if((b[x-1][y]==' ' or b[x+1][y]==' ' or b[x][y-1]==' ' or b[x][y+1]==' ') and (b[x][y]=='.' or b[x][y]=='x')){if(b[x][y]=='x')z--;b[x][y]=' ';}
                else if((b[x-1][y]=='x' or b[x+1][y]=='x' or b[x][y-1]=='x' or b[x][y+1]=='x') and b[x][y]=='.'){z++;b[x][y]='x';}
            }
        cout<<z<<'\n';
    }
    return 0;
}

10/10 W przedostatnim 159 ms 2288, w ostatnim 365 ms 2284.


14 kwi 2011, o 17:33
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: [Architektura niezależna] testy
A mój to już w ogóle nieelegancki:
Kod:
// Kamil Debowski
#include<cstdio>
int z,n,i,r;
char s[1005][1005];
int D(int a,int b)
{
    if(a<0||a>=n||b<0||b>=n) return 0;
    if(s[a][b]=='#') return 0;
    r++;
    s[a][b]='#';
    D(a-1,b);D(a+1,b);D(a,b-1);D(a,b+1);
    return 0;
}
int main()
{
    scanf("%d",&z);
    while(z--){
        scanf("%d",&n); r=0;
        for(i=0;i<n;++i) scanf("%s",s[i]);
        for(i=0;i<n;++i){
            D(0,i);D(i,0);D(n-1,i);D(i,n-1);
        }
        printf("%d\n",n*n-r);
    }
    return 0;
}

Ostatni test 202ms


15 kwi 2011, o 07:42
Zobacz profil
Gwiazda 1

Dołączył(a): 20 lis 2009, o 10:49
Posty: 9
Post Re: [Architektura niezależna] testy
ja niestety nie mialem czasu by to zrobic (praca) kombinowalem jednak przerobic metode wykrywania czy punkt lezy w srodku czy na zewnatrz wielokata


15 kwi 2011, o 16:38
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 49 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4, 5


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL