Ustaw każdą komórkę w macierzy na 0, jeśli ten wiersz lub kolumna zawiera 0

152

Biorąc pod uwagę macierz NxN z 0 i 1. Ustaw każdy wiersz zawierający a 0na wszystkie 0s i ustaw każdą kolumnę zawierającą a 0na wszystkie 0s.

Na przykład

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

prowadzi do

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

Inżynier Microsoft powiedział mi, że istnieje rozwiązanie, które nie wymaga dodatkowej pamięci, tylko dwie zmienne boolowskie i jeden przebieg, więc szukam odpowiedzi.

Przy okazji, wyobraź sobie, że jest to macierz bitowa, dlatego tylko 1s i 0s mogą być w macierzy.

jaircazarin-old-account
źródło
1
Co? Co to jest „kiedy się spotkasz”? W jakiej kolejności napotykasz elementy w macierzy? A jeśli napotkasz wszystkie bity, czy i tak nie otrzymasz wszystkich zer?
ShreevatsaR
Cóż, kolejność, w jakiej zdecydujesz się napotkać elementy, jest twoją decyzją, chodzi o to, że musisz ustawić tylko na 0 odpowiednie elementy. Jeśli napotkasz wszystkie bity ustawione na 0, tak, macierz nadal będzie wypełniona zerami.
stare konto jaircazarin
Co to są „właściwe elementy”? Czy masz dwie macierze, jedną macierz „źródłową”, a drugą macierz „docelową” i musisz zdecydować, w jakiej kolejności „napotykasz” elementy, aby otrzymać macierz „docelową”?
ShreevatsaR
1
Wydaje mi się, że źle usłyszałeś coś przy myśleniu „1 pass”. Można to jednak zrobić liniowo w 2 przebiegach, bez dodatkowej pamięci, tylko 2 booleany ;-) Więc mocno zakładam, że o to właśnie chodziło (patrz poniżej)
Piotr Lesnicki
1
Czy możesz jeszcze raz sprawdzić u znajomego, czy opis problemu jest rzeczywiście prawidłowy? Myślałem, że mogę to zrobić za pomocą kodów Hamminga lub bitów parzystości, ale jak dotąd nie odniosłem sukcesu, a problem wciąż tkwi w mojej głowie. :)
csl

Odpowiedzi:

96

Ok, więc jestem zmęczony, bo tu jest 3 rano, ale mam pierwszą próbę w miejscu z dokładnie 2 przebiegami na każdej liczbie w macierzy, więc w O (NxN) i jest liniowa w rozmiarze matrycy.

Używam pierwszej kolumny i pierwszego wiersza jako znaczników, aby wiedzieć, gdzie są wiersze / kolumny zawierające tylko jedynki. Następnie są 2 zmienne l i c do zapamiętania, jeśli pierwszy wiersz / kolumna to również 1. Tak więc pierwsze przejście ustawia znaczniki, a resztę resetuje do zera.

Drugi przebieg ustawia 1 w miejscach, w których rzędy i kolumny były oznaczone jako 1, i resetuje 1 linię / kolumnę w zależności od l i c.

Wątpię mocno, że da się zrobić w 1 przejściu, ponieważ kwadraty na początku zależą od kwadratów na końcu. Może moje drugie przejście będzie bardziej wydajne ...

import pprint

m = [[1, 0, 1, 1, 0],
     [0, 1, 1, 1, 0],
     [1, 1, 1, 1, 1],
     [1, 0, 1, 1, 1],
     [1, 1, 1, 1, 1]]



N = len(m)

### pass 1

# 1 rst line/column
c = 1
for i in range(N):
    c &= m[i][0]

l = 1
for i in range(1,N):
    l &= m[0][i]


# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][j] == 0:
            m[0][j] = 0
            m[i][0] = 0
        else:
            m[i][j] = 0

### pass 2

# if line1 and col1 are ones: it is 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][0] & m[0][j]:
            m[i][j] = 1

# 1rst row and col: reset if 0
if l == 0:
    for i in range(N):
        m [i][0] = 0

if c == 0:
    for j in range(1,N):
        m [0][j] = 0


pprint.pprint(m)
Piotr Lesnicki
źródło
Jeden problem polega na tym, że jeśli n> sizeof (c) to się psuje. Aby rozszerzyć to tak, aby działało w ogólnym przypadku n, musiałbyś dynamicznie zmienić rozmiar pola bitowego, co moim zdaniem naruszałoby ograniczenie podane przez problem.
Adam
Nie, c nie jest bitfieldem, to po prostu bool. & = Nie jest operacją bitową (cóż, jest, ale na wartości 1-bitowej), jest tam, ponieważ c mówi ci, czy pierwsza kolumna ma wartość 1 (prawda), czy zawiera 0 (fałsz).
Steve Jessop
2
Błąd kończy się niepowodzeniem, jeśli w górnym wierszu jest [0,1,1,1 ...] Moja poprawka polega na zainicjowaniu l do m [0] [0] zamiast 1
paperhorse
rzeczywiście l = 1 dla i w zakresie (1, N): l & = m [0] [i] powinno wynosić l = 1 dla i w zakresie (N): l & = m [0] [i]
Kristof Neirynck
1
Swoją drogą uważam, że warunek w drugim przebiegu powinien wyglądać mniej więcej tak: if m [i] [0] | m [0] [j]:
jaircazarin-old-account
16

Nie można tego zrobić w jednym przebiegu, ponieważ pojedynczy bit ma wpływ na bity przed i po nim w dowolnej kolejności. IOW Niezależnie od kolejności, w jakiej przechodzisz przez tablicę, możesz później napotkać 0, co oznacza, że ​​musisz cofnąć się i zmienić poprzednie 1 na 0.

Aktualizacja

Wydaje się, że ludzie myślą, że ograniczając N do jakiejś stałej wartości (powiedzmy 8), można rozwiązać ten problem w jednym przebiegu. Cóż, to a) pomijam sedno ib) nie jest to oryginalne pytanie. Nie zadałbym pytania na temat sortowania i oczekiwałbym odpowiedzi zaczynającej się od „zakładając, że chcesz posortować tylko 8 rzeczy ...”.

To powiedziawszy, rozsądne podejście jest, jeśli wiesz, że N jest w rzeczywistości ograniczone do 8. Moja odpowiedź powyżej odpowiada na pierwotne pytanie, które nie ma takiego powtórzenia.

Draemon
źródło
Nie da się tego zrobić w jednym przebiegu bez dodatkowej pamięci. Można to zrobić w jednym przebiegu, jeśli jest inna macierz NxN do przechowywania wyników. Podobnie, z kilkoma bitami i dwoma przebiegami można to zrobić bez dodatkowej pamięci.
paxos1977
2
Nadal nie możesz tego zrobić za jednym razem, nawet jeśli używasz tymczasowej matrycy, albo jest coś dziwnego, którego tu nie dostaję. Potrzebujesz jednego przebiegu, aby wydedukować informacje o wierszu / kolumnie, a drugiego, aby ustawić wszystko.
Lasse V. Karlsen
Rozwiązałem ten problem, uznając, że jest tylko jedna unikalna wartość niezerowa możliwa w każdym wierszu i przypisując ją przez odniesienie.
Daniel Papasian,
@ceretullis, lassevk: Nadal uważam, że nie da się tego zrobić za jednym podejściem. Przejścia nad tą drugą matrycą musiałyby się liczyć - w przeciwnym razie możesz po prostu skopiować matrycę w jednym przebiegu i pracować z kopią tak, jak chcesz. @Daniel Papasian: Twoje rozwiązanie nie skaluje się, gdzie N> # bity w int / long / cokolwiek
Draemon
Draemon, technika się skaluje, to tylko matematyka - możesz albo zbudować sprzęt, który to robi, albo możesz użyć technik oprogramowania do manipulowania liczbami większymi niż rozmiar twojego słowa. Żaden z nich nie narusza ograniczeń problemu, IMHO
Daniel Papasian,
10

Więc moim pomysłem jest użycie wartości w ostatnim wierszu / kolumnie jako flagi wskazującej, czy wszystkie wartości w odpowiedniej kolumnie / wierszu to 1.

Za pomocą zygzaka przeskanuj całą macierz Z WYJĄTKIEM ostatniego wiersza / kolumny. W każdym elemencie ustawiasz wartość w ostatnim wierszu / kolumnie jako logiczne AND samego siebie z wartością w bieżącym elemencie. Innymi słowy, jeśli trafisz 0, ostatni wiersz / kolumna zostanie ustawiony na 0. Jeśli wybierzesz 1, wartość w ostatnim wierszu / kolumnie będzie wynosić 1 tylko wtedy, gdy już wynosiła 1. W każdym razie ustaw bieżący element na 0.

Kiedy skończysz, ostatni wiersz / kolumna powinien mieć 1s, jeśli odpowiadająca mu kolumna / wiersz został wypełniony 1s.

Wykonaj liniowe skanowanie ostatniego wiersza i kolumny i wyszukuj jedynki. Ustaw 1 w odpowiednich elementach w treści macierzy, gdzie ostatni wiersz i kolumna to jedynki.

Kodowanie będzie trudne, aby uniknąć błędów typu off-by-one itp., Ale powinno działać w jednym przebiegu.

Alastair
źródło
Bardzo fajnie ... Myślałem nad tymi samymi wierszami, ale przegapiłem użycie ostatniego wiersza / kolumny do przechowywania tych informacji, więc utknąłem z dodatkową pamięcią dla pary tablic Nx1.
Dave Sherohman,
1
Dla mnie wygląda to na dwa przejścia - jedno przejście to zygzak, drugie to „Zestaw 1 w odpowiednich elementach w treści macierzy, gdzie ostatni wiersz i kolumna mają wartości 1”.
Adam Rosenfield
Skan zygzakowaty (który, jak mi ktoś wskazał, nie jest koniecznie konieczny) przechodzi przez wszystko ALE ostatni wiersz / kolumnę. Tak więc skanowanie ostatniej kolumny / wiersza nie powiela wcześniej przeskanowanych elementów. Stąd jedno przejście. Innymi słowy, jest to O (N ^ 2) dla macierzy N * N.
Alastair
6

Mam tutaj rozwiązanie, które działa w jednym przebiegu i wykonuje całe przetwarzanie „na miejscu” bez dodatkowej pamięci (z wyjątkiem powiększania stosu).

Używa rekurencji, aby opóźnić pisanie zer, co oczywiście zniszczyłoby macierz dla innych wierszy i kolumn:

#include <iostream>

/**
* The idea with my algorithm is to delay the writing of zeros
* till all rows and cols can be processed. I do this using
* recursion:
* 1) Enter Recursive Function:
* 2) Check the row and col of this "corner" for zeros and store the results in bools
* 3) Send recursive function to the next corner
* 4) When the recursive function returns, use the data we stored in step 2
*       to zero the the row and col conditionally
*
* The corners I talk about are just how I ensure I hit all the row's a cols,
* I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n).
*
* For simplicities sake, I use ints instead of individual bits. But I never store
* anything but 0 or 1 so it's still fair ;)
*/

// ================================
// Using globals just to keep function
// call syntax as straight forward as possible
int n = 5;
int m[5][5] = {
                { 1, 0, 1, 1, 0 },
                { 0, 1, 1, 1, 0 },
                { 1, 1, 1, 1, 1 },
                { 1, 0, 1, 1, 1 },
                { 1, 1, 1, 1, 1 }
            };
// ================================

// Just declaring the function prototypes
void processMatrix();
void processCorner( int cornerIndex );
bool checkRow( int rowIndex );
bool checkCol( int colIndex );
void zeroRow( int rowIndex );
void zeroCol( int colIndex );
void printMatrix();

// This function primes the pump
void processMatrix() {
    processCorner( 0 );
}

// Step 1) This is the heart of my recursive algorithm
void processCorner( int cornerIndex ) {
    // Step 2) Do the logic processing here and store the results
    bool rowZero = checkRow( cornerIndex );
    bool colZero = checkCol( cornerIndex );

    // Step 3) Now progress through the matrix
    int nextCorner = cornerIndex + 1;
    if( nextCorner < n )
        processCorner( nextCorner );

    // Step 4) Finially apply the changes determined earlier
    if( colZero )
        zeroCol( cornerIndex );
    if( rowZero )
        zeroRow( cornerIndex );
}

// This function returns whether or not the row contains a zero
bool checkRow( int rowIndex ) {
    bool zero = false;
    for( int i=0; i<n && !zero; ++i ) {
        if( m[ rowIndex ][ i ] == 0 )
            zero = true;
    }
    return zero;
}

// This is just a helper function for zeroing a row
void zeroRow( int rowIndex ) {
    for( int i=0; i<n; ++i ) {
        m[ rowIndex ][ i ] = 0;
    }
}

// This function returns whether or not the col contains a zero
bool checkCol( int colIndex ) {
    bool zero = false;
    for( int i=0; i<n && !zero; ++i ) {
        if( m[ i ][ colIndex ] == 0 )
            zero = true;
    }

    return zero;
}

// This is just a helper function for zeroing a col
void zeroCol( int colIndex ) {
    for( int i=0; i<n; ++i ) {
        m[ i ][ colIndex ] = 0;
    }
}

// Just a helper function for printing our matrix to std::out
void printMatrix() {
    std::cout << std::endl;
    for( int y=0; y<n; ++y ) {
        for( int x=0; x<n; ++x ) {
            std::cout << m[y][x] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

// Execute!
int main() {
    printMatrix();
    processMatrix();
    printMatrix();
}
Adam
źródło
2
Niezłe rozwiązanie, ale technicznie rzecz biorąc, używasz więcej pamięci niż dwie dozwolone wartości logiczne (chociaż znajdują się na stosie).
csl
1
To jest> 1 przebieg. Jeśli drukujesz (rowIndex, i) i (i, colIndex), ponieważ są one dostępne w checkRow i checkCol, zobaczysz, że każdy element jest używany wielokrotnie.
Draemon
Draemon: Masz rację, myślę, że potrzebujemy jasnej definicji „pojedynczego przejścia” od twórcy zagadek. Jeśli rzeczywiście ma na myśli, że do każdego elementu można uzyskać dostęp tylko raz, potrzebujemy innego rozwiązania.
Adam
Wyobrażam sobie, że pierwotny problem (który przyszedł do nas przez grę telefoniczną) oznaczał, że problem powinien zostać rozwiązany „na miejscu”, co oznacza, że ​​nie masz kolejnej kopii matrycy. A bardziej optymalne rozwiązania nie wymagają nawet tymczasowej wymiany (), takiej jak pamięć masowa do przetwarzania.
Adam
Wątpię też, czy ograniczenia odnoszą się do powstałego kodu maszynowego. Oznacza to, że podany przeze mnie „kod” wykorzystuje tylko 2 wartości logiczne. W zależności od tego, jakie optymalizacje robi mój kompilator, cała rzecz może być wstawiona lub kto wie, co jeszcze. Myślę, że moje rozwiązanie jest poprawne;)
Adam
4

Myślę, że to nie jest wykonalne. Kiedy jesteś na pierwszym kwadracie, a jego wartość wynosi 1, nie masz możliwości sprawdzenia, jakie są wartości innych kwadratów w tym samym wierszu i kolumnie. Musisz więc je sprawdzić i jeśli jest zero, wróć do pierwszego kwadratu i zmień jego wartość na zero. Polecam zrobić to w dwóch przebiegach - pierwszy przebieg zbiera informacje o tym, które wiersze i kolumny należy wyzerować (informacje są przechowywane w tablicy, więc używamy dodatkowej pamięci). Drugi przebieg zmienia wartości. Wiem, że nie jest to rozwiązanie, którego szukasz, ale myślę, że jest praktyczne. Ograniczenia podane przez Ciebie sprawiają, że problem jest nierozwiązywalny.

Boyan
źródło
Mam prawie to samo rozwiązanie (patrz poniżej) bez dodatkowych tablic. i jest to czas liniowy (ale 2
mijają
@Piotr: Tak, drugie przejście wydaje się nieuniknione. Wprowadzenie tablic do przechowywania informacji o wierszach i kolumnach, które zaproponowałem, sprawia, że ​​algorytm jest prostszy i nieco szybszy, ponieważ jest mniej sprawdzania i zmiany wartości. To kompromis między pamięcią masową a wydajnością.
Boyan
3

Mogę to zrobić z dwiema zmiennymi całkowitymi i dwoma przebiegami (do 32 wierszy i kolumn ...)

bool matrix[5][5] = 
{ 
    {1, 0, 1, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {1, 0, 1, 1, 1},
    {1, 1, 1, 1, 1}
};

int CompleteRows = ~0;
int CompleteCols = ~0;

// Find the first 0
for (int row = 0; row < 5; ++row)
{
    for (int col = 0; col < 5; ++col)
    {
        CompleteRows &= ~(!matrix[row][col] << row);
        CompleteCols &= ~(!matrix[row][col] << col);
    }
}

for (int row = 0; row < 5; ++row)
    for (int col = 0; col < 5; ++col)
        matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col));
Zaćmienie
źródło
Czy to jest C #? Co oznacza ~?
sker
To jest C ++. ~odwraca wszystkie bity w zmiennej. 0x00000000 staje się 0x00000000. Zasadniczo zaczynam od wszystkich i usuwam bit dla wiersza / kolumny, gdy znajdę 0. CompleteCols ma ustawione bity 2 i 3, a CompleteRows ma ustawione bity 2 i 4 (oparte na 0).
Eclipse
Następnie wystarczy ustawić bity w macierzy odpowiadające bitom w obu CompleteCols i CompleteRows.
Eclipse
3

problem można rozwiązać za jednym razem

zapis macierzy w tablicy i X j.

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1 
1 1 1 1 1

one each pass save the values of i and j for an element which is 0 in arrays a and b
when first row is scanned a= 1 b = 2,5
when second row is scanned a=1,2 b= 1,2,5
when third row is scanned no change
when fourth row is scanned a= 1,2,4 and b= 1,2,5
when fifth row is scanned no change .

teraz wypisz wszystkie wartości jako 0 dla wartości i i j zapisanych w aib pozostałe wartości to 1 tj. (3,3) (3,4) (5,3) i (5,4)

siddharth
źródło
1

Innym rozwiązaniem, które wymaga dwóch przebiegów, jest gromadzenie AND w poziomie i w pionie:

1 0 1 1 0 | 0
0 1 1 1 0 | 0
1 1 1 1 1 | 1
1 0 1 1 1 | 0
1 1 1 1 1 | 1
----------+
0 0 1 1 0    

Pomyślałem, że mógłbym zaprojektować taki algorytm przy użyciu bitów parzystości , kodów Hamminga lub programowania dynamicznego , prawdopodobnie używając tych dwóch wartości logicznych jako liczby 2-bitowej, ale nie odniosłem jeszcze sukcesu.

Czy możesz ponownie sprawdzić opis problemu ze swoim inżynierem i powiadomić nas o tym? Jeśli tam jest rzeczywiście rozwiązaniem, chcę zachować Zmniejszanie problemu.

csl
źródło
1

Zachowaj jedną zmienną, aby śledzić, jakie są wszystkie wiersze połączone operatorem AND.

Jeśli wiersz ma wartość -1 (wszystkie jedynki), ustaw następny wiersz jako odniesienie do tej zmiennej

Jeśli wiersz jest czymś innym niż 0. Możesz zrobić wszystko za jednym razem. Kod pseudo:

foreach (my $row) rows {
     $andproduct = $andproduct & $row;
     if($row != -1) {
        zero out the row
     }  else {
        replace row with a reference to andproduct
     }
}

To powinno wystarczyć w jednym przebiegu - ale jest tu założenie, że N jest wystarczająco małe, aby procesor mógł wykonać operacje arytmetyczne w jednym wierszu, w przeciwnym razie będziesz musiał zapętlić każdy wiersz, aby określić, czy to wszystko 1 s lub nie, jak sądzę. Ale biorąc pod uwagę, że pytasz o algorytmy i nie ograniczasz mojego sprzętu, mógłbym po prostu rozpocząć swoją odpowiedź od „Zbuduj procesor obsługujący arytmetykę N-bitową ...”

Oto jeden przykład, jak można to zrobić w C. Uwaga: Twierdzę, że wartości i arr wzięte razem reprezentują tablicę, a p i numproduct są moim iteratorem, a zmienne iloczynu AND służą do implementacji problemu. (Mogłem zapętlić arr z arytmetyką wskaźników, aby sprawdzić poprawność mojej pracy, ale raz wystarczył!)

int main() {
    int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */
    int *arr[5] = { values, values+1, values+2, values+3, values+4 };
    int **p;
    int numproduct = 127;

    for(p = arr; p < arr+5; ++p) {
        numproduct = numproduct & **p;
        if(**p != -1) {
            **p = 0;
        } else {
            *p = &numproduct;
        }
    }

    /* Print our array, this loop is just for show */
    int i;
    for(i = 0; i < 5; ++i) {
        printf("%x\n",*arr[i]);
    }
    return 0;
}

Daje to 0, 0, 6, 0, 6, co jest wynikiem dla podanych danych wejściowych.

Lub w PHP, jeśli ludzie uważają, że moje gry na stackach w C oszukują (sugeruję, że tak nie jest, ponieważ powinienem móc przechowywać macierz w dowolny sposób):

<?php

$values = array(-10, 14, -1, -9, -1);
$numproduct = 127;

for($i = 0; $i < 5; ++$i) {
    $numproduct = $numproduct & $values[$i];
    if($values[$i] != -1) {
        $values[$i] = 0;
    } else {
        $values[$i] = &$numproduct;
    }
}

print_r($values);

Czy coś mi brakuje?

Daniel Papasian
źródło
To nie działa, jeśli N jest większe niż liczba bitów w int / long / cokolwiek, więc nie sądzę, że to się liczy.
Draemon
Nie wykryje również rzeczy, jeśli 0 znajdują się na dole tablicy (spróbuj z wartościami [] = {-1, -9, -1, 14, -10}).
Eclipse
Draemon, w mojej odpowiedzi określam, że bez ograniczeń sprzętowych w ramach pytania zaczynasz od „Zbuduj procesor obsługujący arytmetykę N-bitową”.
Daniel Papasian
Josh, nie nadążam. Dzięki rozwiązaniu C lub PHP i zasugerowanej tablicy otrzymuję 6 0 6 0 0, co moim zdaniem jest poprawną odpowiedzią.
Daniel Papasian,
@Daniel - Nie możesz, ponieważ N nie jest stałą. Poza tym „zbudowanie nowego komputera ze słowami 1Mbit nie jest rozsądnym krokiem algorytmicznym.
Draemon,
1

Niezłe wyzwanie. To rozwiązanie używa tylko dwóch wartości logicznych utworzonych na stosie, ale wartości logiczne są tworzone kilka razy na stosie, ponieważ funkcja jest rekurencyjna.

typedef unsigned short     WORD;
typedef unsigned char      BOOL;
#define true  1
#define false 0
BYTE buffer[5][5] = {
1, 0, 1, 1, 0,
0, 1, 1, 1, 0,
1, 1, 1, 1, 1,
1, 0, 1, 1, 1,
1, 1, 1, 1, 1
};
int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N)
{
    WORD i;
    for(i=0;i<N;i++)
    {
        if(!buffer[i][pos_N])
            *h=false;
        if(!buffer[pos_N][i])
            *w=false;
    }
    return 0;
}
int set_line(BOOL h,BOOL w,WORD N,WORD pos_N)
{
    WORD i;
    if(!h)
        for(i=0;i<N;i++)
            buffer[i][pos_N] = false;
    if(!w)
        for(i=0;i<N;i++)
            buffer[pos_N][i] = false;
    return 0;
}
int scan(int N,int pos_N)
{
    BOOL h = true;
    BOOL w = true;
    if(pos_N == N)
        return 0;
    // Do single scan
    scan_to_end(&h,&w,N,pos_N);
    // Scan all recursive before changeing data
    scan(N,pos_N+1);
    // Set the result of the scan
    set_line(h,w,N,pos_N);
    return 0;
}
int main(void)
{
    printf("Old matrix\n");
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
    scan(5,0);
    printf("New matrix\n");
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
    system( "pause" );
    return 0;
}

To skanuje w następujący sposób:

s,s,s,s,s
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0


0,s,0,0,0
s,s,s,s,s
0,s,0,0,0
0,s,0,0,0
0,s,0,0,0

i tak dalej

A następnie zmiana wartości w tym wzorze po powrocie dla każdej z funkcji skanowania. (Od dołu do góry):

0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
c,c,c,c,c


0,0,0,c,0
0,0,0,c,0
0,0,0,c,0
c,c,c,c,c
0,0,0,c,0

i tak dalej

eaanon01
źródło
Wydaje mi się, że to nie jest poprawne, ponieważ nadal zużywasz znacznie więcej niż dwie wartości logiczne na swoim stosie.
csl
Jak mi przykro z dwóch booleów. To jest najbliższa specyfikacji, o której mogę pomyśleć. Bardzo chciałbym zobaczyć tutaj rzeczywiste rozwiązanie. Jeśli to możliwe.
eaanon01
Nie sądzę, żeby wymagania odnosiły się do powiększania stosu. Myślę, że jest to doskonale uzasadnione rozwiązanie.
Adam
To też jest moja myśl. Ale nie mogę być pewien, dopóki ktoś inny nie opublikuje lepszego rozwiązania. Przynajmniej moje rozwiązanie jest kompilowalne i każdy może je zweryfikować. :) ... Nie mam znaleźć kodu psudo dla praktycznych problemów. Thnx
eaanon01
1

Okej, to jest rozwiązanie

  • wykorzystuje tylko jedną bardzo długą wartość do przechowywania roboczego.
  • nie używa rekursji.
  • jeden przebieg tylko N, nawet nie N * N.
  • będzie działać dla innych wartości N, ale będzie potrzebować nowych #defines.
#include <stdio.h>
#define BIT30 (1<<24)
#define COLMASK 0x108421L
#define ROWMASK 0x1fL
unsigned long long STARTGRID = 
((0x10 | 0x0 | 0x4 | 0x2 | 0x0) << 20) |
((0x00 | 0x8 | 0x4 | 0x2 | 0x0) << 15) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 10) |
((0x10 | 0x0 | 0x4 | 0x2 | 0x1) << 5) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 0);


void dumpGrid (char* comment, unsigned long long theGrid) {
    char buffer[1000];
    buffer[0]='\0';
    printf ("\n\n%s\n",comment);
    for (int j=1;j<31; j++) {
        if (j%5!=1)
            printf( "%s%s", ((theGrid & BIT30)==BIT30)? "1" : "0",(((j%5)==0)?"\n" : ",") );    
        theGrid = theGrid << 1;
    }
}

int main (int argc, const char * argv[]) {
    unsigned long long rowgrid = STARTGRID;
    unsigned long long colGrid = rowgrid;

    unsigned long long rowmask = ROWMASK;
    unsigned long long colmask = COLMASK;

    dumpGrid("Initial Grid", rowgrid);
    for (int i=0; i<5; i++) {
        if ((rowgrid & rowmask)== rowmask) rowgrid |= rowmask;
        else rowgrid &= ~rowmask;
        if ((colGrid & colmask) == colmask) colmask |= colmask;
        else colGrid &=  ~colmask;
        rowmask <<= 5;
        colmask <<= 1;
    }
    colGrid &= rowgrid;
    dumpGrid("RESULT Grid", colGrid);
    return 0;
    }
AnthonyLambert
źródło
Z pewnością jest to miłe rozwiązanie. I przypuszczam, że każde z tych rozwiązań pomija przynajmniej jeden z wymagań. Tak więc posiadanie rozwiązania z maksymalną dopuszczalną wartością N nie jest najgorszą rzeczą na świecie, więc niezła robota :)
Adam
Ograniczenie N do 8 i twierdzenie, że spełnia to warunek jednego przejścia, jest po prostu głupie. To nie jest rozwiązanie ogólne. W pytaniu nie podano ograniczenia rozmiaru N, więc rozwiązałeś tylko podproblem.
Draemon,
ale wszystkie te rozwiązania mają ograniczenie N w taki czy inny sposób.
AnthonyLambert
Mówienie, że jest to jedno przejście N, jest oczywiście całkowicie błędne. Nawet samo odczytanie wartości każdej pozycji w oryginalnej macierzy to O (N ^ 2) i zdecydowanie konieczne jest odczytanie wartości na każdej pozycji przynajmniej raz, aby móc obliczyć rozwiązanie. Nawet jeśli przechowujesz wartości jako pojedyncze bity przez długi czas, dostęp do każdego bitu będzie miał wartość O (N ^ 2), ponieważ jest O (N ^ 2) bitów.
Alderath,
Jest to oczywiście jeden przebieg, gdy wartość RowGrid przechowuje całą siatkę i po pierwszym odczycie byłby jednym z rejestrów procesora dla całego algorytmu, jeśli optymalizator jest dobry.
AnthonyLambert
1

Tak właściwie. Jeśli chcesz tylko uruchomić algorytm i wydrukować wyniki (tj. Nie je przywrócić, możesz to łatwo zrobić w jednym przebiegu) .Kłopot pojawia się, gdy próbujesz zmodyfikować tablicę w trakcie wykonywania algorytmu.

Oto moje rozwiązanie. Po prostu polega na połączeniu wartości wierszy / kolumn dla elementu Givein (i, j) i wydrukowaniu go.

#include <iostream>
#include "stdlib.h"

void process();

int dim = 5;
bool m[5][5]{{1,0,1,1,1},{0,1,1,0,1},{1,1,1,1,1},{1,1,1,1,1},{0,0,1,1,1}};


int main() {
    process();
    return 0;
}

void process() {
    for(int j = 0; j < dim; j++) {
        for(int i = 0; i < dim; i++) {
            std::cout << (
                          (m[0][j] & m[1][j] & m[2][j] & m[3][j] & m[4][j]) &
                          (m[i][0] & m[i][1] & m[i][2] & m[i][3] & m[i][4])
                          );
        }
        std::cout << std::endl;
    }
}
Kenny Cason
źródło
1

Próbowałem rozwiązać ten problem w C #.

Użyłem dwóch zmiennych pętli (i i j) oprócz rzeczywistej macierzy in reprezentującej jej wymiar

Logika, której próbowałem:

  1. Oblicz AND dla wierszy i cols zaangażowanych w każdy koncentryczny kwadrat macierzy
  2. Przechowuj go w komórkach narożnych (zapisałem je w kolejności przeciwnej do ruchu wskazówek zegara)
  3. Dwie zmienne bool są używane do zachowania wartości dwóch rogów podczas obliczania konkretnego kwadratu.
  4. Ten proces zakończy się, gdy zewnętrzna pętla (i) znajdzie się w połowie drogi.
  5. Oceń wyniki innych komórek na podstawie komórek narożnych (do końca i). Pomiń komórki narożne podczas tego procesu.
  6. Kiedy osiągnę n, wszystkie komórki miałyby swój wynik z wyjątkiem komórek narożnych.
  7. Zaktualizuj komórki narożne. Jest to dodatkowa iteracja do długości n / 2, inna niż ograniczenie pojedynczego przejścia, o którym mowa w zadaniu.

Kod:

void Evaluate(bool [,] matrix, int n)
{
    bool tempvar1, tempvar2;

    for (var i = 0; i < n; i++)
    {
        tempvar1 = matrix[i, i];
        tempvar2 = matrix[n - i - 1, n - i - 1];

        var j = 0;

        for (j = 0; j < n; j++)
        {
            if ((i < n/2) || (((n % 2) == 1) && (i == n/2) && (j <= i)))
            {
                // store the row and col & results in corner cells of concentric squares
                tempvar1 &= matrix[j, i];
                matrix[i, i] &= matrix[i, j];
                tempvar2 &= matrix[n - j - 1, n - i - 1];
                matrix[n - i - 1, n - i - 1] &= matrix[n - i - 1, n - j - 1];
            }
            else
            {
                // skip corner cells of concentric squares
                if ((j == i) || (j == n - i - 1)) continue;

                // calculate the & values for rest of them
                matrix[i, j] = matrix[i, i] & matrix[n - j - 1, j];
                matrix[n - i - 1, j] = matrix[n - i - 1, n - i - 1] & matrix[n - j - 1, j];

                if ((i == n/2) && ((n % 2) == 1))
                {
                    // if n is odd
                    matrix[i, n - j - 1] = matrix[i, i] & matrix[j, n - j - 1];
                }
            }
        }

        if ((i < n/2) || (((n % 2) == 1) && (i <= n/2)))
        {
            // transfer the values from temp variables to appropriate corner cells of its corresponding square
            matrix[n - i - 1, i] = tempvar1;
            matrix[i, n - i - 1] = tempvar2;
        }
        else if (i == n - 1)
        {
            // update the values of corner cells of each concentric square
            for (j = n/2; j < n; j++)
            {
                tempvar1 = matrix[j, j];
                tempvar2 = matrix[n - j - 1, n - j - 1];

                matrix[j, j] &= matrix[n - j - 1, j];
                matrix[n - j - 1, j] &= tempvar2;

                matrix[n - j - 1, n - j - 1] &= matrix[j, n - j - 1];
                matrix[j, n - j - 1] &= tempvar1;
            }
        }
    }
}
BK
źródło
1

One Pass - przeszedłem dane wejściowe tylko raz, ale użyłem nowej tablicy i tylko dwóch dodatkowych zmiennych boolowskich.

public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();

        boolean rowDel = false, colDel = false;
        int arr[][] = new int[n][n];
        int res[][] = new int[n][n];
        int i, j;
        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
                res[i][j] = arr[i][j];  
            }
        }

        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {
                if (arr[i][j] == 0)
                    colDel = rowDel = true; //See if we have to delete the
                                            //current row and column
                if (rowDel == true){
                    res[i] = new int[n];
                    rowDel = false;
                }
                if(colDel == true){
                    for (int k = 0; k < n; k++) {
                        res[k][j] = 0;
                    }
                    colDel = false;
                }

            }

        }

        for (i = 0; i < n; i++) {

            for (j = 0; j < n; j++) {
                System.out.print(res[i][j]);
            }
            System.out.println();
        }
        sc.close();

    }
RahulDeep Attri
źródło
0

Chociaż jest to niemożliwe, biorąc pod uwagę ograniczenia, najbardziej efektywnym przestrzennie sposobem na to jest przechodzenie przez matrycę w sposób nakładający się, naprzemienny rząd / kolumna, co dałoby wzór podobny do układania cegieł w zygzak:

-----
|----
||---
|||--
||||-

Używając tego, przejdziesz do każdego wiersza / kolumny, jak wskazano, i jeśli napotkasz 0 w dowolnym momencie, ustaw zmienną logiczną i ponownie przejrzyj ten wiersz / kolumnę, ustawiając wpisy na 0.

Nie będzie to wymagało dodatkowej pamięci i użyje tylko jednej zmiennej boolowskiej. Niestety, jeśli „daleka” krawędź jest ustawiona na 0, jest to najgorszy przypadek i przechodzisz przez całą tablicę dwa razy.

cdeszaq
źródło
Mogę się mylić, ale czy na pewno to działa? Kiedy robisz trzecią kolumnę, powiedz, skąd wiesz, czy wartość na jej początku, w pierwszym wierszu, była 1 lub 0 przed przetworzeniem pierwszego wiersza?
Steve Jessop
Nie wiesz, ale też nie musisz. Jeśli było to 0, cała kolumna musi mieć wartość 0. Jeśli wartość w poprzednim wierszu wynosi 1, wiesz, że wszystkie wiersze powyżej to 1 (i zawsze były).
Dave Sherohman
0

utwórz macierz wyników i ustaw wszystkie wartości na 1. przejdź przez macierz danych, gdy tylko zostanie napotkane 0, ustaw kolumnę wiersza macierzy wyników na 0

Pod koniec pierwszego przejścia macierz wyników będzie zawierała poprawną odpowiedź.

Wygląda całkiem prosto. Czy brakuje mi jakiejś sztuczki? Czy nie możesz używać zestawu wyników?

EDYTOWAĆ:

Wygląda jak funkcja F #, ale to trochę oszukuje, ponieważ nawet jeśli wykonujesz pojedynczy przebieg, funkcja może być rekurencyjna.

Wygląda na to, że ankieter próbuje dowiedzieć się, czy znasz programowanie funkcjonalne.

mson
źródło
1
Korzystanie z zestawu wyników wymagałoby dodatkowej pamięci.
cdeszaq
Programowanie funkcjonalne nie modyfikowałoby oryginalnej tablicy w miejscu.
Svante
0

Cóż, wymyśliłem jednoprzebiegowe, na miejscu (nierekurencyjne) rozwiązanie wykorzystujące 4 boole i 2 liczniki pętli. Nie udało mi się zredukować go do 2 booli i 2 int, ale nie zdziwiłbym się, gdyby to było możliwe. Wykonuje około 3 odczytów i 3 zapisów dla każdej komórki i powinno być O (N ^ 2) tj. liniowy w rozmiarze tablicy.

Rozwikłanie tego rozwiązania zajęło mi kilka godzin - nie chciałbym wymyślać tego pod presją wywiadu! Jeśli zrobiłem booboo, jestem zbyt zmęczony, żeby to zauważyć ...

Um ... Zdecydowałem się zdefiniować „jednoprzebiegowe” jako wykonanie jednego przeciągnięcia po macierzy, zamiast dotykania każdej wartości raz! :-)

#include <stdio.h>
#include <memory.h>

#define SIZE    5

typedef unsigned char u8;

u8 g_Array[ SIZE ][ SIZE ];

void Dump()
{
    for ( int nRow = 0; nRow < SIZE; ++nRow )
    {
        for ( int nColumn = 0; nColumn < SIZE; ++nColumn )
        {
            printf( "%d ", g_Array[ nRow ][ nColumn ] );
        }
        printf( "\n" );
    }
}

void Process()
{
    u8 fCarriedAlpha = true;
    u8 fCarriedBeta = true;
    for ( int nStep = 0; nStep < SIZE; ++nStep )
    {
        u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true;
        u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true;
        fAlpha &= g_Array[ nStep ][ nStep ];
        fBeta &= g_Array[ nStep ][ nStep ];
        g_Array[ nStep-1 ][ nStep ] = fCarriedBeta;
        g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha;
        for ( int nScan = nStep + 1; nScan < SIZE; ++nScan )
        {
            fBeta &= g_Array[ nStep ][ nScan ];
            if ( nStep > 0 )
            {
                g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ];
                g_Array[ nStep-1][ nScan ] = fCarriedBeta;
            }

            fAlpha &= g_Array[ nScan ][ nStep ];
            if ( nStep > 0 )
            {
                g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ];
                g_Array[ nScan ][ nStep-1] = fCarriedAlpha;
            }
        }

        g_Array[ nStep ][ nStep ] = fAlpha & fBeta;

        for ( int nScan = nStep - 1; nScan >= 0; --nScan )
        {
            g_Array[ nScan ][ nStep ] &= fAlpha;
            g_Array[ nStep ][ nScan ] &= fBeta;
        }
        fCarriedAlpha = fAlpha;
        fCarriedBeta = fBeta;
    }
}

int main()
{
    memset( g_Array, 1, sizeof(g_Array) );
    g_Array[0][1] = 0;
    g_Array[0][4] = 0;
    g_Array[1][0] = 0;
    g_Array[1][4] = 0;
    g_Array[3][1] = 0;

    printf( "Input:\n" );
    Dump();
    Process();
    printf( "\nOutput:\n" );
    Dump();

    return 0;
}

źródło
0

Mam nadzieję, że spodoba Ci się moje jednoprzebiegowe rozwiązanie C #

możesz pobrać element za pomocą O (1) i potrzebujesz tylko miejsca na jeden wiersz i jedną kolumnę macierzy

bool[][] matrix =
{
    new[] { true, false, true, true, false }, // 10110
    new[] { false, true, true, true, false }, // 01110
    new[] { true, true, true, true, true },   // 11111
    new[] { true, false, true, true, true },  // 10111
    new[] { true, true, true, true, true }    // 11111
};

int n = matrix.Length;
bool[] enabledRows = new bool[n];
bool[] enabledColumns = new bool[n];

for (int i = 0; i < n; i++)
{
    enabledRows[i] = true;
    enabledColumns[i] = true;
}

for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
    for (int columnIndex = 0; columnIndex < n; columnIndex++)
    {
        bool element = matrix[rowIndex][columnIndex];
        enabledRows[rowIndex] &= element;
        enabledColumns[columnIndex] &= element;
    }
}

for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
    for (int columnIndex = 0; columnIndex < n; columnIndex++)
    {
        bool element = enabledRows[rowIndex] & enabledColumns[columnIndex];
        Console.Write(Convert.ToInt32(element));
    }
    Console.WriteLine();
}

/*
    00000
    00000
    00110
    00000
    00110
*/
Nacięcie
źródło
Myślę, że jedynym problemem może być to, że używasz dwóch dodatkowych tablic danych, aby to zadziałało. Jednym z warunków jest niewykorzystywanie dodatkowej pamięci. Ale fajnie! to w zasadzie to, co zrobiłem w mojej odpowiedzi :)
Kenny Cason,
0

1 przebieg, 2 wartości logiczne. Muszę tylko założyć, że indeksy całkowite w iteracjach się nie liczą.

To nie jest kompletne rozwiązanie, ale nie mogę przejść tego punktu.

Gdybym tylko mógł określić, czy 0 jest oryginalnym 0, czy 1, które zostało przekonwertowane na 0, nie musiałbym używać -1 i to zadziałałoby.

Moje wyniki wyglądają następująco:

-1  0 -1 -1  0
 0 -1 -1 -1  0
-1 -1  1  1 -1
-1  0 -1 -1 -1
-1 -1  1  1 -1

Oryginalność mojego podejścia polega na wykorzystaniu pierwszej połowy badania wiersza lub kolumny do określenia, czy zawiera 0, a ostatniej połowy do ustawienia wartości - odbywa się to poprzez spojrzenie na x i szerokość-x, a następnie y i wysokość -y w każdej iteracji. Opierając się na wynikach pierwszej połowy iteracji, jeśli znaleziono 0 w wierszu lub kolumnie, używam ostatniej połowy iteracji, aby zmienić 1 na -1.

Właśnie zdałem sobie sprawę, że można to zrobić mając tylko 1 wartość logiczną, która pozostawia 1 do ...?

Publikuję to, mając nadzieję, że ktoś powie: „Ach, po prostu zrób to ...” (I spędziłem zbyt dużo czasu, żeby nie publikować).

Oto kod w VB:

Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}}

Dim B1, B2 As Boolean

For y As Integer = 0 To UBound(D)

    B1 = True : B2 = True

    For x As Integer = 0 To UBound(D)

        // Scan row for 0's at x and width - x positions. Halfway through I'll konw if there's a 0 in this row.
        //If a 0 is found set my first boolean to false.
        If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
            If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False
        End If

        //If the boolean is false then a 0 in this row was found. Spend the last half of this loop
        //updating the values. This is where I'm stuck. If I change a 1 to a 0 it will cause the column
        //scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if
        //the value had changed this would work.
        If Not B1 Then
            If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
                If D(x, y) = 1 Then D(x, y) = -1
                If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1
            End If
        End If

        //These 2 block do the same as the first 2 blocks but I switch x and y to do the column.
        If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
            If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False
        End If

        If Not B2 Then
            If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
                If D(y, x) = 1 Then D(y, x) = -1
                If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1
            End If
        End If

    Next
Next
rvarcher
źródło
0

Nikt nie używa formularzy binarnych? ponieważ jest to tylko 1 i 0. Możemy używać wektorów binarnych.

def set1(M, N):
    '''Set 1/0s on M according to the rules.

    M is a list of N integers. Each integer represents a binary array, e.g.,
    000100'''
    ruler = 2**N-1
    for i,v in enumerate(M):
        ruler = ruler & M[i]
        M[i] = M[i] if M[i]==2**N-1 else 0  # set i-th row to all-0 if not all-1s
    for i,v in enumerate(M):
        if M[i]: M[i] = ruler
    return M

Oto test:

M = [ 0b10110,
      0b01110,
      0b11111,
      0b10111,
      0b11111 ]

print "Before..."
for i in M: print "{:0=5b}".format(i)

M = set1(M, len(M))
print "After..."
for i in M: print "{:0=5b}".format(i)

A wynik:

Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
KFL
źródło
0

Możesz zrobić coś takiego, aby użyć jednego przebiegu, ale macierzy wejścia i wyjścia:

output(x,y) = col(xy) & row(xy) == 2^n

gdzie col(xy)jest bitami w kolumnie zawierającej punkt xy; row(xy)to bity w wierszu zawierającym punkt xy. njest rozmiarem macierzy.

Następnie po prostu wykonaj pętlę nad wejściem. Czy istnieje możliwość rozbudowy, aby zajmować więcej miejsca?

Warbum
źródło
0

Jeden skan macierzy, dwie wartości logiczne, bez rekursji.

Jak uniknąć drugiego przejścia? Drugie przejście jest potrzebne do wyczyszczenia wierszy lub kolumn, gdy na ich końcu pojawi się zero.

Jednak ten problem można rozwiązać, ponieważ kiedy skanujemy wiersz #i, znamy już stan wiersza dla wiersza # i-1. Tak więc, podczas skanowania wiersza #i, możemy jednocześnie wyczyścić wiersz # i-1, jeśli jest to potrzebne.

To samo rozwiązanie działa dla kolumn, ale musimy skanować wiersze i kolumny jednocześnie, podczas gdy dane nie są zmieniane przez kolejną iterację.

Do przechowywania stanu pierwszego wiersza i pierwszej kolumny wymagane są dwie wartości logiczne, ponieważ ich wartości zostaną zmienione podczas wykonywania głównej części algorytmu.

Aby uniknąć dodawania większej liczby wartości logicznych, przechowujemy flagę „wyczyść” dla wierszy i kolumn w pierwszym wierszu i kolumnie macierzy.

public void Run()
{
    const int N = 5;

    int[,] m = new int[N, N] 
                {{ 1, 0, 1, 1, 0 },
                { 1, 1, 1, 1, 0 },
                { 1, 1, 1, 1, 1 },
                { 1, 0, 1, 1, 1 },
                { 1, 1, 1, 1, 1 }};

    bool keepFirstRow = (m[0, 0] == 1);
    bool keepFirstColumn = keepFirstRow;

    for (int i = 1; i < N; i++)
    {
        keepFirstRow = keepFirstRow && (m[0, i] == 1);
        keepFirstColumn = keepFirstColumn && (m[i, 0] == 1);
    }

    Print(m); // show initial setup

    m[0, 0] = 1; // to protect first row from clearing by "second pass"

    // "second pass" is performed over i-1 row/column, 
    // so we use one more index just to complete "second pass" over the 
    // last row/column
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            // "first pass" - searcing for zeroes in row/column #i
            // when i = N || j == N it is additional pass for clearing 
            // the previous row/column
            // j >= i because cells with j < i may be already modified 
            // by "second pass" part
            if (i < N && j < N && j >= i) 
            {
                m[i, 0] &= m[i, j];
                m[0, j] &= m[i, j];

                m[0, i] &= m[j, i];
                m[j, 0] &= m[j, i];
            }

            // "second pass" - clearing the row/column scanned 
            // in the previous iteration
            if (m[i - 1, 0] == 0 && j < N)
            {
                m[i - 1, j] = 0;
            }

            if (m[0, i - 1] == 0 && j < N)
            {
                m[j, i - 1] = 0;
            }
        }

        Print(m);
    }

    // Clear first row/column if needed
    if (!keepFirstRow || !keepFirstColumn)
    {
        for (int i = 0; i < N; i++)
        {
            if (!keepFirstRow)
            {
                m[0, i] = 0;
            }
            if (!keepFirstColumn)
            {
                m[i, 0] = 0;
            }
        }
    }

    Print(m);

    Console.ReadLine();
}

private static void Print(int[,] m)
{
    for (int i = 0; i < m.GetLength(0); i++)
    {
        for (int j = 0; j < m.GetLength(1); j++)
        {
            Console.Write(" " + m[i, j]);
        }
        Console.WriteLine();
    }
    Console.WriteLine();
}
Artemix
źródło
0

wygląda na to, że następujące prace nie wymagają dodatkowego miejsca:

Najpierw zauważ, że pomnożenie elementów wiersza razy elementów wiersza, w którym znajduje się element, daje żądaną wartość.

Aby nie używać dodatkowej przestrzeni (nie tworzyć nowej macierzy i wypełniać ją, ale zamiast tego bezpośrednio wprowadzać zmiany w macierzy), należy rozpocząć od lewej górnej części macierzy i wykonać obliczenia dla dowolnej macierzy ixi (która „zaczyna się” od (0 , 0)) przed rozważeniem dowolnego elementu o dowolnym indeksie> i.

mam nadzieję, że to zadziała (nie mam testu)

DFF
źródło
Wydaje się być niepoprawne. Załóżmy, że wiersz 0 ma tylko 1 wartość. Jeśli końcowa wartość ustawiona dla (0,0) to 0, później ustawisz cały wiersz na 0, co niekoniecznie jest poprawne. W rzeczywistości musisz przechowywać 2 wartości na komórkę, aby zrobić to w dynamicznym stylu programowania, używając Twojej zasady.
Eyal Schneider
jasne, masz rację. Zamiast zapamiętywać dwie wartości, mógłbym też użyć trzeciej możliwości, powiedzmy -1, która oznacza komórki, które są 1 w "starej" macierzy, które ostatecznie zostaną zastąpione przez 0. Oczywiście w ten sposób trzeba przyjąć wartość bezwzględną wartości po mnożeniu. W końcu wszystkie -1 są zastępowane przez 0.
DFF,
0

Jest to TESTOWANE dla różnych N w C ++ i jest:
JEDNO PRZEJŚCIE , DWA BOOLE , BEZ REKURSJI , BEZ DODATKOWEJ PAMIĘCI , PRZYSŁUGUJE SIĘ NA DROBNO DUŻE N
(Póki co żadne z przedstawionych tutaj rozwiązań nie obsługuje WSZYSTKICH).

Mówiąc dokładniej, zabawne są dwa liczniki pętli. Mam dwie const unsigneds, które istnieją tylko zamiast być obliczane za każdym razem dla czytelności. Interwał pętli zewnętrznej to [0, N], a przedział pętli wewnętrznej to [1, n - 1]. Instrukcja switch jest w pętli głównie po to, aby bardzo wyraźnie pokazać, że tak naprawdę jest to tylko jeden przebieg.

Strategia algorytmu:

Pierwszą sztuczką jest dla nas wiersz i kolumna z samej macierzy, aby zgromadzić zawartość macierzy, ta pamięć staje się dostępna poprzez przeniesienie wszystkiego, co naprawdę musimy wiedzieć, z pierwszego wiersza i kolumny na dwie wartości logiczne. Druga sztuczka polega na uzyskaniu dwóch przebiegów z jednego, używając symetrii podmacierzy i jej indeksów.

Streszczenie algorytmu:

  • Przeskanuj pierwszy wiersz i zapisz, jeśli wszystkie są wartościami logicznymi, zrób to samo dla pierwszej kolumny, przechowując wynik w drugiej wartości logicznej.
  • W przypadku macierzy podrzędnej z wyłączeniem pierwszego wiersza i pierwszej kolumny: iteruj od lewej do prawej, od góry do dołu, tak jak czyta się akapit. Odwiedzając każdy element, odwiedź również odpowiedni element, który zostałby odwiedzony, gdyby odwiedzono podmacierz w odwrotnej kolejności. Dla każdego odwiedzanego elementu ORAZ jego wartości do miejsca, w którym jego wiersz przecina pierwszą kolumnę, a także ORAZ jego wartości do miejsca, w którym jego kolumna przecina pierwszy wiersz.
  • Po osiągnięciu środka podmacierzy kontynuuj odwiedzanie dwóch elementów jednocześnie, jak powyżej. Jednak teraz ustaw wartość odwiedzanych elementów na AND, gdzie jego wiersz przecina pierwszą kolumnę i gdzie jego kolumna przecina pierwszy wiersz. Następnie podmacierz jest kompletna.
  • Użyj dwóch zmiennych logicznych obliczonych na początku, aby ustawić pierwszy wiersz i pierwszą kolumnę na ich prawidłowe wartości.

Implementacja w języku C ++ oparta na szablonach:

template<unsigned n>
void SidewaysAndRowColumn(int((&m)[n])[n]) {
    bool fcol = m[0][0] ? true : false;
    bool frow = m[0][0] ? true : false;
    for (unsigned d = 0; d <= n; ++d) {
        for (unsigned i = 1; i < n; ++i) {
            switch (d) {
                case 0:
                    frow    = frow && m[d][i];
                    fcol    = fcol && m[i][d];
                    break;
                default:
                {
                    unsigned const rd = n - d;
                    unsigned const ri = n - i;
                    if (d * n + i < rd * n + ri)
                    {
                        m[ d][ 0] &= m[ d][ i];
                        m[ 0][ d] &= m[ i][ d];
                        m[ 0][ i] &= m[ d][ i];
                        m[ i][ 0] &= m[ i][ d];
                        m[rd][ 0] &= m[rd][ri];
                        m[ 0][rd] &= m[ri][rd];
                        m[ 0][ri] &= m[rd][ri];
                        m[ri][ 0] &= m[ri][rd];
                    }
                    else
                    {
                        m[ d][ i] = m[ d][0] & m[0][ i];
                        m[rd][ri] = m[rd][0] & m[0][ri];
                    }
                    break;
                }
                case n:
                    if (!frow)
                        m[0][i] = 0;
                    if (!fcol)
                        m[i][0] = 0;
            };
        }
    }
    m[0][0] = (frow && fcol) ? 1 : 0;
}
Apriori
źródło
0

Ok, zdaję sobie sprawę, że to nie do końca pasuje, ale otrzymałem to w jednym przebiegu, używając bool i bajtu zamiast dwóch bool ... blisko. Nie ręczyłbym również za jego skuteczność, ale tego typu pytania często wymagają mniej niż optymalnych rozwiązań.

private static void doIt(byte[,] matrix)
{
    byte zeroCols = 0;
    bool zeroRow = false;

    for (int row = 0; row <= matrix.GetUpperBound(0); row++)
    {
        zeroRow = false;
        for (int col = 0; col <= matrix.GetUpperBound(1); col++)
        {
            if (matrix[row, col] == 0)
            {

                zeroRow = true;
                zeroCols |= (byte)(Math.Pow(2, col));

                // reset this column in previous rows
                for (int innerRow = 0; innerRow < row; innerRow++)
                {
                    matrix[innerRow, col] = 0;
                }

                // reset the previous columns in this row
                for (int innerCol = 0; innerCol < col; innerCol++)
                {
                    matrix[row, innerCol] = 0;
                }
            }
            else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0)
            {
                matrix[row, col] = 0;
            }

            // Force the row to zero
            if (zeroRow) { matrix[row, col] = 0; }
        }
    }
}
Walery Strauch
źródło
0

Możesz to zrobić w jednym przebiegu - jeśli nie liczysz dostępu do matrycy w kolejności losowej, co eliminuje korzyści płynące z robienia tego w jednym przejściu (spójność pamięci podręcznej / przepustowość pamięci).

[edytuj: usunięto proste, ale złe rozwiązanie]

Powinieneś uzyskać lepszą wydajność niż jakakolwiek metoda jednoprzebiegowa, wykonując to w dwóch przebiegach: jeden do gromadzenia informacji o wierszach / kolumnach, a drugi do ich zastosowania. Dostęp do tablicy (w kolejności wiersz-główny) jest spójny; dla tablic przekraczających rozmiar pamięci podręcznej (ale których wiersze mieszczą się w pamięci podręcznej), dane powinny być odczytywane z pamięci dwukrotnie i zapisywane raz:

void fixmatrix2(int M[][], int rows, int cols) {
    bool clearZeroRow= false;
    bool clearZeroCol= false;
    for(int j=0; j < cols; ++j) {
        if( ! M[0][j] ) {
            clearZeroRow= true;
        }
    }
    for(int i=1; i < rows; ++i) { // scan/accumulate pass
        if( ! M[i][0] ) {
            clearZeroCol= true;
        }
        for(int j=1; j < cols; ++j) {
            if( ! M[i][j] ) {
                M[0][j]= 0;
                M[i][0]= 0;
            }
        }
    }
    for(int i=1; i < rows; ++i) { // update pass
        if( M[i][0] ) {
            for(int j=0; j < cols; ++j) {
                if( ! M[j][0] ) {
                    M[i][j]= 0;
                }
            }
        } else {
            for(int j=0; j < cols; ++j) {
                M[i][j]= 0;
            }
        }
        if(clearZeroCol) {
            M[i][0]= 0;
        }
    }
    if(clearZeroRow) {
        for(int j=0; j < cols; ++j) {
            M[0][j]= 0;
        }
    }
}
nadchodząca burza
źródło
0

Najprostsze rozwiązanie, jakie przychodzi mi do głowy, jest wklejone poniżej. Logika polega na zapisaniu, który wiersz i kolumna mają ustawić zero podczas iteracji.

import java.util.HashSet;
import java.util.Set;

public class MatrixExamples {
    public static void zeroOut(int[][] myArray) {
        Set<Integer> rowsToZero = new HashSet<>();
        Set<Integer> columnsToZero = new HashSet<>();

        for (int i = 0; i < myArray.length; i++) { 
            for (int j = 0; j < myArray.length; j++) {
                if (myArray[i][j] == 0) {
                    rowsToZero.add(i);
                    columnsToZero.add(j);
                }
            }
        }

        for (int i : rowsToZero) {
            for (int j = 0; j < myArray.length; j++) {
                myArray[i][j] = 0;
            }
        }

        for (int i : columnsToZero) {
            for (int j = 0; j < myArray.length; j++) {
                myArray[j][i] = 0;
            }
        }

        for (int i = 0; i < myArray.length; i++) { // record which rows and                                             // columns will be zeroed
            for (int j = 0; j < myArray.length; j++) {
                System.out.print(myArray[i][j] + ",");
            if(j == myArray.length-1)
                System.out.println();
            }
        }

    }

    public static void main(String[] args) {
        int[][] a = { { 1, 0, 1, 1, 0 }, { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1 },
                { 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 1 } };
        zeroOut(a);
    }
}
geekprogrammer
źródło
0

Oto moja implementacja Ruby z dołączonym testem, zajęłoby to miejsce O (MN). Jeśli chcemy aktualizacji w czasie rzeczywistym (np. Aby pokazać wyniki, gdy znajdziemy zera, zamiast czekać na pierwszą pętlę znajdowania zer), możemy po prostu utworzyć inną zmienną klasy, jak @outputi zawsze, gdy znajdziemy zero, aktualizujemy, @outputa nie @input.

require "spec_helper"


class Matrix
    def initialize(input)
        @input  = input
        @zeros  = []
    end

    def solve
        @input.each_with_index do |row, i|          
            row.each_with_index do |element, j|                             
                @zeros << [i,j] if element == 0
            end
        end

        @zeros.each do |x,y|
            set_h_zero(x)
            set_v_zero(y)
        end

        @input
    end


    private 

    def set_h_zero(row)     
        @input[row].map!{0}     
    end

    def set_v_zero(col)
        @input.size.times do |r|
            @input[r][col] = 0
        end
    end
end


describe "Matrix" do
  it "Should set the row and column of Zero to Zeros" do
    input =  [[1, 3, 4, 9, 0], 
              [0, 3, 5, 0, 8], 
              [1, 9, 6, 1, 9], 
              [8, 3, 2, 0, 3]]

    expected = [[0, 0, 0, 0, 0],
                [0, 0, 0, 0, 0],
                [0, 9, 6, 0, 0],
                [0, 0, 0, 0, 0]]

    matrix = Matrix.new(input)

    expect(matrix.solve).to eq(expected)
  end
end
Eki Eqbal
źródło
0

Poniższy kod tworzy macierz o rozmiarze m, n. Najpierw zdecyduj o wymiarach macierzy. Chciałem wypełnić macierz [m] [n] losowo liczbami z zakresu 0..10. Następnie utwórz kolejną macierz o tych samych wymiarach i wypełnij ją -1s (ostateczna macierz). Następnie wykonaj iterację przez początkową macierz, aby zobaczyć, czy trafisz 0. Kiedy trafisz w położenie (x, y), przejdź do ostatniej macierzy i wypełnij wiersz x zerami, a kolumnę y zerami. Na koniec przeczytaj końcową macierz, jeśli wartość wynosi -1 (wartość oryginalna), skopiuj wartość w tym samym miejscu początkowej macierzy do ostatecznej.

public static void main(String[] args) {
    int m = 5;
    int n = 4;
    int[][] matrixInitial = initMatrix(m, n); // 5x4 matrix init randomly
    int[][] matrixFinal = matrixNull(matrixInitial, m, n); 
    for (int i = 0; i < m; i++) {
        System.out.println(Arrays.toString(matrixFinal[i]));
    }
}

public static int[][] matrixNull(int[][] matrixInitial, int m, int n) {
    int[][] matrixFinal = initFinal(m, n); // create a matrix with mxn and init it with all -1
    for (int i = 0; i < m; i++) { // iterate in initial matrix
        for (int j = 0; j < n; j++) {
            if(matrixInitial[i][j] == 0){ // if a value is 0 make rows and columns 0
                makeZeroX(matrixFinal, i, j, m, n); 
            }
        }
    }

    for (int i = 0; i < m; i++) { // if value is -1 (original) copy from initial
        for (int j = 0; j < n; j++) {
            if(matrixFinal[i][j] == -1) {
                matrixFinal[i][j] = matrixInitial[i][j];
            }
        }
    }
    return matrixFinal;
}

private static void makeZeroX(int[][] matrixFinal, int x, int y, int m, int n) {
        for (int j = 0; j < n; j++) { // make all row 0
            matrixFinal[x][j] = 0;
        }
        for(int i = 0; i < m; i++) { // make all column 0
            matrixFinal[i][y] = 0; 
        }
}

private static int[][] initMatrix(int m, int n) {

    int[][] matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            Random rn = new Random();
            int random = rn.nextInt(10);
            matrix[i][j] = random;
        }
    }

    for (int i = 0; i < m; i++) {
        System.out.println(Arrays.toString(matrix[i]));
    }
    System.out.println("******");
    return matrix;
}

private static int[][] initFinal(int m, int n) {

    int[][] matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = -1;
        }
    }
    return matrix;
}

// another approach
/**
 * @param matrixInitial
 * @param m
 * @param n
 * @return
 */
private static int[][] matrixNullNew(int[][] matrixInitial, int m, int n) {
    List<Integer> zeroRowList = new ArrayList<>(); // Store rows with 0
    List<Integer> zeroColumnList = new ArrayList<>(); // Store columns with 0
    for (int i = 0; i < m; i++) { // read through the matrix when you hit 0 add the column to zeroColumnList and add
                                  // the row to zeroRowList
        for (int j = 0; j < n; j++) {
            if (matrixInitial[i][j] == 0) {
                if (!zeroRowList.contains(i)) {
                    zeroRowList.add(i);
                }
                if (!zeroColumnList.contains(j)) {
                    zeroColumnList.add(j);
                }
            }
        }
    }

    for (int a = 0; a < m; a++) {
        if (zeroRowList.contains(a)) { // if the row has 0
            for (int b = 0; b < n; b++) {
                matrixInitial[a][b] = 0; // replace all row with zero
            }
        }
    }

    for (int b = 0; b < n; b++) {
        if (zeroColumnList.contains(b)) { // if the column has 0
            for (int a = 0; a < m; a++) {
                matrixInitial[a][b] = 0; // replace all column with zero
            }
        }
    }
    return matrixInitial;
}
user3743369
źródło
Nie podajesz żadnych wyjaśnień ani kontekstu opublikowanego kodu.
Aaron
Mam nadzieję, że teraz jest lepiej. Dzięki za ostrzeżenie. Chciałbym wyjaśnić więcej, jeśli nie jest to dla Ciebie jasne.
user3743369
0

oto moje rozwiązanie. Jak widać z kodu, biorąc pod uwagę macierz M * N, ustawia ona cały wiersz na zero po sprawdzeniu zera w tym wierszu. Złożoność czasowa mojego rozwiązania wynosi O (M * N). Udostępniam całą klasę, która ma statyczną wypełnioną tablicę do testowania i metodę tablicy wyświetlania, aby zobaczyć wynik w konsoli.

public class EntireRowSetToZero {
    static int arr[][] = new int[3][4];
    static {

    arr[0][0] = 1;
    arr[0][1] = 9;
    arr[0][2] = 2;
    arr[0][3] = 2;

    arr[1][0] = 1;
    arr[1][1] = 5;
    arr[1][2] = 88;
    arr[1][3] = 7;

    arr[2][0] = 0;
    arr[2][1] = 8;
    arr[2][2] = 4;
    arr[2][3] = 4;
}

public static void main(String[] args) {
    displayArr(EntireRowSetToZero.arr, 3, 4);
    setRowToZero(EntireRowSetToZero.arr);
    System.out.println("--------------");
    displayArr(EntireRowSetToZero.arr, 3, 4);


}

static int[][] setRowToZero(int[][] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if(arr[i][j]==0){
                arr[i]=new int[arr[i].length];
            }
        }

    }
    return arr;
}

static void displayArr(int[][] arr, int n, int k) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < k; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.println("");
    }

}

}

Türkmen Mustafa Demirci
źródło