|
Wątki bez odpowiedzi | Aktywne wątki
[Architektura niezależna] testy
| Autor |
Wiadomość |
|
Dołączył(a): 7 paź 2010, o 20:33
Posty: 43
|
 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: Dla wzorku: 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 
|
| 14 kwi 2011, o 10:28 |
|
|
|
Dołączył(a): 11 paź 2010, o 10:02
Posty: 83
|
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 |
|
|
|
Dołączył(a): 15 cze 2010, o 19:01
Posty: 11
|
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 |
|
|
|
Dołączył(a): 12 paź 2010, o 17:37
Posty: 4
|
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
|
| 14 kwi 2011, o 13:57 |
|
|
|
Dołączył(a): 11 paź 2010, o 10:02
Posty: 83
|
Re: [Architektura niezależna] testy 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 |
|
|
|
Dołączył(a): 25 lut 2010, o 20:19
Posty: 69
|
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 
|
| 14 kwi 2011, o 16:22 |
|
|
|
Dołączył(a): 2 sie 2010, o 20:56
Posty: 27
|
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 |
|
|
|
Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
|
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 |
|
|
|
Dołączył(a): 20 lis 2009, o 10:49
Posty: 9
|
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 |
|
|
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
|
|
