Установите каждую ячейку в матрице к 0, если та строка или столбец содержат 0

Можно отсортировать, делают это в одной передаче - если Вы не считаете доступ к матрице в порядке произвольного доступа, который устраняет преимущества выполнения его однопроходный во-первых (cache-coherence/memory-bandwidth).

[редактирование: простое, но неверное решение удалило]

, необходимо получить лучшую производительность, чем какой-либо однопроходный метод путем выполнения его в двух передачах: один для накопления строки/информации о столбце, и один для применения его. К массиву (в главном строкой порядке) получают доступ когерентно; для массивов, превышающих размер кэша (но чьи строки могут поместиться в кэш), данные должны быть считаны из памяти дважды и сохранены однажды:

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;
        }
    }
}

Хорошо, я понимаю, что это не настоящее соответствие, но я попал в точку передача с помощью bool и байта вместо двух bools... закрыть. Я также не ручался бы за эффективность его, но эти типы вопросов часто требуют меньше, чем оптимальные решения.

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; }
        }
    }
}

я надеюсь, что Вы наслаждаетесь моей 1 передачей c# решение

, можно получить элемент с O (1) и только нуждаться в пространстве одной строки и одном столбце матрицы

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
*/

Другой решение, которое берет две передачи, состоит в том, чтобы накопить ANDs горизонтально и вертикально:

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    

я думал, что мог разработать такой алгоритм с помощью динамическое программирование Кодов Хемминга или битов четности , , возможно с помощью тех двух булевских переменных в качестве 2-разрядного числа, но я еще не имел никакого успеха.

можно ли перепроверить проблемный оператор с инженером и сообщить ли нам? Если там действительно решение, я хочу держать производство микросхем отдельно в проблеме.

создайте матрицу результата и установите все значения к 1. пройдите матрицу данных, как только с 0 встречаются, установите столбец строки матрицы результата на 0

В конце первой передачи, матрица результата будет иметь корректный ответ.

довольно простые Взгляды. Существует ли прием, который я пропускаю? Разве Нельзя использовать набор результатов?

РЕДАКТИРОВАНИЕ:

Похож на функцию F#, но это обманывает немного, с тех пор даже при том, что Вы делаете единственную передачу, функция может быть рекурсивной.

похоже, что интервьюер пытается выяснить, знаете ли Вы функциональное программирование.

В то время как невозможный, учитывая ограничения, большая часть пространства эффективный способ сделать это путем пересечения матрицы в накладывании, переменном виде строки/столбец, который сделал бы шаблон подобным наложению кирпичей зигзагообразным способом:

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

Используя это, Вы вошли бы в каждую строку/столбец, как обозначено, и если Вы встречаетесь с 0 когда-либо, устанавливаете логическую переменную и переобход, что строка/столбец, устанавливая записи в 0, когда Вы идете.

Это не потребует никакой дополнительной памяти и будет только использовать одну логическую переменную. К сожалению, если "далекий" край установлен на все быть 0, который является худшим случаем, и Вы обходите целый массив дважды.

Хорошо это - решение что

• использование всего одно дополнительное длинное значение для рабочей памяти.
• использование никакая рекурсия.
• одна передача только N, даже N*N.
• будет работать на другие значения N, но будет нуждаться в новом #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;
    }

Хорошая проблема. Этот вид решения использования всего две булевские переменные, созданные на стеке, но булевских переменных, несколько раз создаются на стеке, так как функция является рекурсивной.

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;
}

Это сканирует в шаблоне как:

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

и так далее

И затем changeing значения в этом шаблоне по возврату на каждой из функций сканирования. (Вверх дном):

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

и так далее

Сохраните единственную переменную для отслеживания то, каковы все строки ANDed вместе.

, Если строка-1 (вся 1 с), то сделайте следующую строку ссылкой на ту переменную

, Если строка совсем не, это - 0. Можно сделать все в одной передаче. Psuedo-код:

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

, Который должен сделать это в единственной передаче - но существует предположение здесь, что N является достаточно маленьким для ЦП, чтобы сделать арифметику на единственной строке, еще Вы собираетесь должны циклично выполниться по каждой строке, чтобы определить, является ли это вся 1 с или нет, я верю. Но, учитывая Вы спрашиваете об алгоритмах и не ограничиваете мои аппаратные средства, я только запустил бы свой ответ со "Сборки ЦП, который поддерживает арифметику N-bit..."

Вот один пример, как он может быть сделан в C. Обратите внимание, что я утверждаю, что значения и прибытие, взятое вместе, представляют массив, и p и numproduct являются моим итератором и И использование переменных продукта для реализации проблемы. (Я, возможно, циклично выполнился по прибытию с адресной арифметикой с указателями для проверки моей работы, но однажды был достаточно!)

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;
}

Это производит 0, 0, 6, 0, 6, который является результатом для данных исходных данных.

Или в PHP, если люди думают, мои игры стека в C обманывают (я намекаю Вам, что это не, потому что я должен быть в состоянии сохранить матрицу, какой бы ни путь мне нравится):

<?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);

я пропускаю что-то?

Я могу сделать это с двумя целочисленными переменными и двумя передачами (до 32 строк и столбцы...)

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));

Ну, я предложил однопроходное, оперативное (нерекурсивное) решение с помощью 4 bools и 2 счетчиков цикла. Мне не удалось уменьшить его до 2 bools и 2 ints, но я не был бы удивлен, было ли это возможно. Это делает приблизительно 3 чтения и 3 записи каждой ячейки, и это должен быть O (N^2) т.е. линейный в размере массива.

Взял меня несколько часов для разрешения этого - я не захочу должным быть придумывать его под давлением интервью! Если я сделал ляп, я также устал для определения его...

Гм... Я принимаю решение определить "однопроходный" как создание одной развертки через матрицу, вместо того, чтобы коснуться каждого значения однажды!:-)

#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;
}

У меня есть решение здесь, оно работает в единственной передаче и делает всю обработку "на месте" без дополнительной памяти (сохраните для роста стека).

Это использует рекурсию для задержки записи нулей, которые, конечно, уничтожили бы матрицу для других строк и седел:

#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();
}

Я не думаю, что это выполнимо. Когда Вы находитесь на первом квадрате, и его значение равняется 1, у Вас нет способа знать, каковы значения других квадратов в той же строке и столбце. Таким образом, необходимо проверить тех и если существует нуль, возвратитесь в первый квадрат и измените его значение для обнуления. Я рекомендую делать его в двух передачах - первая передача собирает информацию, о которой строки и столбцы должны быть обнулены (информация хранится в массиве, таким образом, мы используем некоторую дополнительную память). Вторая передача изменяет значения. Я знаю, что это не решение, которое Вы ищете, но я думаю, что это - практическое. Ограничения, данные Вами, представляют неразрешимую проблему.

Таким образом, моя идея состоит в том, чтобы использовать значения в последней строке/столбец как флаг, чтобы указать, являются ли все значения в соответствующем столбце/строке 1 с.

Используя сканирование Резкого поворота Крутого поворота через всю матрицу КРОМЕ заключительной строки/столбец. В каждом элементе Вы устанавливаете значение в заключительной строке/столбец относительно логического И себя со значением в элементе тока. Другими словами, при ударе 0 заключительная строка/столбец будет установлена на 0. Если Вы это, которым 1, значение в заключительной строке/столбец будет 1, только если это уже было 1. В любом случае установите элемент тока на 0.

, Когда Вы закончили, Ваша заключительная строка/столбец должна иметь 1 эквивалентность с, соответствующий столбец/строка был заполнен 1 с.

Делают линейное сканирование через заключительную строку и столбец и поиск 1 с. Установите 1 с в соответствующих элементах в теле матрицы, где заключительная строка и столбец являются оба 1 с.

Кодирование это будет хитро для предотвращения ошибок диапазона и т.д., но это должно работать в одной передаче.

Это не может быть сделано в одной передаче, так как единственный бит имеет эффект на биты прежде и после нее в любом упорядочивании. IOW Безотносительно порядка, в котором Вы пересекаете массив, можно позже приехать через 0, что означает, что необходимо возвратиться и изменить предыдущий 1 на 0.

Обновление

Люди, кажется, думают, что путем ограничения N к некоторому фиксированному значению (говорят 8) можно решить, это - одна передача. Хорошо это a) упускает суть и b) исходный вопрос. Я не отправил бы вопрос на сортировке и ожидал бы ответ, который начал "предполагать, что Вы только хотите отсортировать 8 вещей...".

Однако это - разумный подход, если Вы знаете, что N на самом деле ограничивается 8. Мой ответ выше отвечает на исходный вопрос, который не имеет такого ограничения.

1 проход, 2 логических значения. Я просто должен предположить, что целочисленные индексы в итерациях не учитываются.

Это не полное решение, но я не могу пройти эту точку.

Если бы я мог только определить, является ли 0 оригинальным 0 или 1, который был преобразован в 0, тогда мне не пришлось бы использовать -1, и это работало бы.

Мой вывод выглядит так:

-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

Оригинальность моего подхода заключается в использовании первой половины проверки строки или столбца, чтобы определить, содержит ли она 0, а в последней половине - для установки значений - это делается путем просмотра x и width-x, а затем y и height-y в каждой итерации. Основываясь на результатах первой половины итерации, если в строке или столбце был найден 0, я использую последнюю половину итерации, чтобы изменить 1 на -1.

Я только что понял, что это может быть сделано только с одним логическим значением, оставляющим от 1 до ...?

Я публикую это в надежде, что кто-то скажет: «А, просто сделай это ...» (И я потратил слишком много много времени на нем не публиковать.)

Вот код в 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