Escriba un programa o función que tome una cadena multilínea de 0'sy 1' s. No habrá otros caracteres en la cadena y la cadena siempre será rectangular (todas las líneas tendrán el mismo número de caracteres), con dimensiones tan pequeñas como 1 × 1, pero de lo contrario las 0'sy 1' pueden estar dispuestas arbitrariamente.

Puede suponer que la cadena tiene una nueva línea final opcional, y si lo desea, puede usar dos caracteres ASCII imprimibles distintos en lugar de 0y 1.

Imprima o devuelva un valor verdadero si todas las regiones conectadas a la ruta de ambos 0's y 1' s en la cadena son rectángulos sólidos , de lo contrario genera un valor falso .

Una región de ruta conectada0 significa que desde cualquiera 0de la región, 0se puede llegar a todas las demás moviéndose solo hacia arriba, hacia abajo, hacia la izquierda y hacia la derecha hacia las de otras personas 0(y sin moverse en diagonal, sin moverse hacia ninguna 1, y no se mueve fuera de los límites de la cadena). La misma idea se aplica a las 1regiones conectadas por ruta.

Un rectángulo sólido de 0's significa que toda el área del rectángulo está llena de 0' sy no 1'. La misma idea se aplica a 1los rectángulos sólidos.

El código más corto en bytes gana. Tiebreaker es la respuesta anterior.

(Tenga en cuenta que la cadena no se ajusta a las condiciones de contorno toroidales ).

Ejemplos

1) Esta cadena de entrada tiene 3 regiones conectadas a la ruta (2 para 0y 1 para 1). Sin 00embargo, solo la región inferior derecha es un rectángulo sólido, por lo que la salida sería falsa.

0011
0111
0100

2) Esta cadena de entrada tiene 4 regiones conectadas a la ruta (2 para ambos 0y 1). Todos ellos son rectángulos sólidos, por lo que el resultado sería verdadero.

0011
0011
1100

3) Esta entrada tiene 2 regiones conectadas a la ruta, pero solo una de ellas es un rectángulo sólido, por lo que la salida sería falsa.

00000000
01111110
00000000

4) Esta entrada tiene solo 1 región conectada a la ruta y es trivialmente un rectángulo sólido, por lo que la salida es verdadera.

11111111
11111111
11111111

Casos de prueba

Un Tpoco debajo de la cadena de entrada significa verdadero, Fsignifica falso.

0
T

1
T

00
T

01
T

10
T

11
T

0000000
T

1111111
T

011100100100101100110100100100101010100011100101
T

00
11
T

01
10
T

01
11
F

00
01
F

11
11
T

110
100
F

111
000
T

111
101
111
F

101
010
101
T

1101
0010
1101
0010
T

1101
0010
1111
0010
F

0011
0111
0100
F

0011
0011
1100
T

00000000
01111110
00000000
F

11111111
11111111
11111111
T

0000001111
0000001111
T

0000001111
0000011111
F

0000001111
1000001111
F

1000001111
1000001111
T

1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F

Jalea , 7 bytes

ṣ⁷µ=ḢZE

Utiliza el mismo algoritmo que la respuesta Ruby de @ LevelRiverSt . El algoritmo real cabe en los últimos 4 bytes; Los primeros 3 bytes son necesarios para analizar el formato de entrada.

Pruébalo en línea!

Cómo funciona

ṣ⁷µ=ḢZE  Main link. Argument: t (string)

ṣ⁷       Split t at linefeeds..
  µ      Begin a new, monadic link. Argument: A (list of strings)
    Ḣ    Pop the first string of A.
   =     Compare all other strings in A with the first.
         = compares characters, so this yields a list of Booleans for each string.
         For a truthy input, all pairs of lines now have been transformed in lists
         of only 1's or only 0's. That means all columns must be equal.
     Z   Zip; transpose rows with columns.
      E  Check if all rows (former columns) are equal to each other.

Jalea , 11 10 bytes

ṣ⁷^2\⁺€FS¬

Muchas gracias a @Dennis por jugar golf hasta la mitad de su tamaño original (a través de funciones no documentadas).

Pruébalo en línea ! Tenga en cuenta que las comillas triples son para una cadena multilínea.

Explicación

El algoritmo básico es: devuelve verdadero si cada subcuadrícula 2x2 tiene un número par de 1s (o, equivalentemente, 0s).

Está claro por qué un número impar de 1s no puede funcionar, ya que tendríamos uno de los siguientes:

10  01  00  00  01  10  11  11
00  00  01  10  11  11  10  01

Tenga en cuenta que los primeros 4 son rotaciones de la misma cosa, y lo mismo ocurre con los últimos 4. El ángulo reflejo no puede ser parte de un rectángulo, de ahí que sea inválido.

En otras palabras, todas las subcuadrículas 2x2 deben ser una de las siguientes:

00  00  11  01  10  01  10  11
00  11  00  01  10  10  01  11

que, si miramos los límites, puede imaginarse como las siguientes "piezas de rompecabezas":

 ___    ___    ___    ___
|   |  | | |  |   |  | | |
|   |  | | |  |---|  |-|-|
|___|  |_|_|  |___|  |_|_|

E intente formar un no rectángulo con esas piezas de rompecabezas :) (mientras los extremos coinciden)

La implementación real es así:

ṣ⁷               Split input by newlines to give rows
  ^2\            Taking overlapping sets of 2 rows at a time: accumulate rows by XOR
                 Note that strings cast to integers automatically for bitwise operators
     ⁺€          Repeat the previous link (⁺), on each (€) element in the resulting array
       F         Flatten the array
        S        Sum (effectively reducing by OR)
         ¬       Logical negation of the result

Por ejemplo, para la entrada

100
010
000
101

tenemos:

  ṣ⁷: ["100", "010", "000", "101"]
 ^2\: [[1, 1, 0], [0, 1, 0], [1, 0, 1]]    (e.g. first entry is "100" ^ "010")
^2\€: [[0, 1], [1, 1], [1, 1]]             (e.g. the first entry is [1^1, 1^0] - this
                                            gives the counts of 1s in each subgrid, mod 2)
   F: [0, 1, 1, 1, 1, 1]
   S: 5                                    (this gives the number of invalid 2x2 subgrids,
                                            which is indeed all but the top left)
   ¬: 0

Ruby, 76

->s{j=!r=1
s.lines{|t|i=t.to_i(2)
j&&r&&=(j^i)%t.tr(?0,?1).to_i(2)<1
j=i}
r}

En cualquier cuadrícula compuesta completamente de rectángulos, cada línea debe ser idéntica a la línea anterior, o tener todos los bits invertidos de 0 a 1 y viceversa.

Esto es fácil de probar. Tome un trozo de papel y dibuje líneas arbitrarias verticales y horizontales a través de él. Ahora colorea los rectángulos usando solo 2 colores. Terminará con un tablero de ajedrez distorsionado, donde todos los colores cambian en cada línea.

¿Desea dibujar rectángulos con líneas solo en parte? intente eliminar un segmento de cualquiera de sus líneas. Ahora necesitará más de 2 colores para colorear su diseño, porque tendrá puntos donde se encuentran 3 rectángulos (2 esquinas y un borde). Por lo tanto, tales diseños son irrelevantes para esta pregunta.

Estoy sorprendido de que las respuestas hasta ahora no hayan notado esto.

Creo que este algoritmo debería ser mucho más corto en algún otro idioma.

Sin golf en el programa de prueba

f=->s{
  j=!r=1                              #r = truthy, j=falsy
  s.lines{|t|                         #for each line
    i=t.to_i(2)                       #i = value of current line, converted to a number in base 2 (binary)
    j&&                               #if j is truthy (i.e this is not the first line)
      r&&=(j^i)%t.tr(?0,?1).to_i(2)<1 #XOR i with the previous line. Take the result modulo (current line with all 0 replaced by 1)
                                      #if the result of the XOR was all 0 or all 1, the modulo == zero (<1). Otherwise, it will be a positive number.   
j=i}                                  #j = value of current line (always truthy in ruby, even if zero)
r}                                    #return 1 or true if all the modulo calculations were zero, else false.



#text to print after test case to check answer is as desired
T='T

'
F='F

'

#test cases
puts f['0'],T

puts f['1'],T

puts f['00
'],T

puts f['01'],T

puts f['10'],T

puts f['11
'],T

puts f['0000000'],T

puts f['1111111'],T

puts f['011100100100101100110100100100101010100011100101'],T

puts f['00
11'],T

puts f['01
10'],T


puts f['01
11'],F

puts f['00
01'],F

puts f['11
11
'],T

puts f['110
100'],F

puts f['111
000'],T

puts f['111
101
111'],F

puts f['101
010
101
'],T

puts f['1101
0010
1101
0010'],T

puts f['1101
0010
1111
0010'],F

puts f['0011
0111
0100
'],F

puts f['0011
0011
1100'],T

puts f['00000000
01111110
00000000'],F

puts f['11111111
11111111
11111111'],T

puts f['0000001111
0000001111'],T

puts f['0000001111
0000011111'],F

puts f['0000001111
1000001111'],F

puts f['1000001111
1000001111'],T

puts f['1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111'],F

Caracoles , 20 bytes

!{to{\0w`3\1|\1w`3\0

Imprime el área de la cuadrícula si no hay un cuadrado de 2x2 con 3 ceros y uno o 3 unos y un cero, o 0si existe un cuadrado de 2x2.

MATL , 12 bytes

Ybc2thYCs2\~

Mismo algoritmo que la gran respuesta de @ sp3000 .

Para permitir la entrada multilínea, MATL necesita que la matriz de caracteres de fila (cadena) se construya explícitamente usando el carácter 10de nueva línea. Entonces, la entrada de los cuatro ejemplos es (tenga en cuenta que []es una concatenación, por lo que cada uno de estos es una matriz de filas de caracteres):

['0011' 10 '0111' 10 '0100']
['0011' 10 '0011' 10 '1100']
['00000000' 10 '01111110' 10 '00000000']
['11111111' 10 '11111111' 10 '11111111']

y los últimos tres casos de prueba son

['0000001111' 10 '1000001111']
['1000001111' 10 '1000001111']
['1110100110101010110100010111011101000101111' 10 '1010100100101010100100010101010101100101000' 10 '1110100110010010110101010111010101010101011' 10 '1010100100101010010101010110010101001101001' 10 '1010110110101010110111110101011101000101111']

La salida de verdad es una matriz que contiene solo unos.

Pruébalo en línea!

Explicación

Esto utiliza el hecho de que la paridad de caracteres '0'y '1'es la misma que la de los números 0y 1, por lo tanto, no es necesario convertir de char al dígito que representa,

Yb     % split implicit input by whitespace. Gives a cell array
c      % concatenate cell contents into 2D char array
2th    % push array [2 2]
YC     % get 2×2 sliding blocks and arrange as columns
s      % sum of each column
2\     % modulo 2 of each sum
~      % negate. Implicit display

JavaScript (ES6), 69 bytes

s=>!s.split`
`.some((t,i,u)=>[...t].some((v,j)=>v^t[0]^u[0][j]^s[0]))

Creo que el criterio del rectángulo de conectividad de ruta es equivalente a exigir que, dados los cuatro puntos que forman las esquinas de un rectángulo arbitrario, haya un número par de 1s. Tenga en cuenta que la paridad del rectángulo (0, b), (x, y) es la misma que (0, b), (a, y) ^(a, b), (x, y), así que solo tengo que verificar esos rectángulos cuya esquina superior izquierda está en (0, 0). También según las leyes de De Morgan, !.some()es lo mismo .every(!)que me ahorra un par de bytes.

Editar: me doy cuenta de que la solución Jelly verifica la paridad de las esquinas de todos los rectángulos 2 × 2, que pueden ser equivalentes.

JavaScript (ES6), 79

Mismo algoritmo de respuesta de Jelly de @ Sp3000 (y feliz de no tener que demostrar que funciona). Solo 8 veces más

s=>[...s].every((x,i)=>[++i,i+=s.search`
`,i+1].some(p=>!(x^=p=s[p],p>`
`))|!x) 

Menos golf

s=>[...s].every((x,i)=> // repeat check for every sub square
     [++i,                  // array of position for next char in row
      i+=s.search`\n`, i+1] // and 2 chars at same column in next row
       .some(p=> // for each position 
          !( 
            x^=s[p],  // xor current value with value at position p
            s[p]>`\n` // true if value at position p is valid
           ) // the condition is negated
       ) // if any value scanned is not valid, .some return true
         // else, we must consider the check for current square
       | !x // x can be 0 or 1, to be valid must be 0
   ) 

Banco de pruebas

f=s=>[...s].every((x,i)=>[++i,i+=s.search`
`,i+1].some(p=>!(x^=p=s[p],p>`
`))|!x) 

testData=`
0
T

1
T

00
T

01
T

10
T

11
T

0000000
T

1111111
T

011100100100101100110100100100101010100011100101
T

00
11
T

01
10
T

01
11
F

00
01
F

11
11
T

110
100
F

111
000
T

111
101
111
F

101
010
101
T

1101
0010
1101
0010
T

1101
0010
1111
0010
F

0011
0111
0100
F

0011
0011
1100
T

00000000
01111110
00000000
F

11111111
11111111
11111111
T

0000001111
0000001111
T

0000001111
0000011111
F

0000001111
1000001111
F

1000001111
1000001111
T

1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F`

console.log=x=>O.textContent+=x+'\n'

testData.split('\n\n').forEach(t=>{
  var k=t.slice(-1)=='T',
      r=f(t.slice(0,-1))
  console.log(t+' '+r+ (k==r?' OK\n':' KO\n'))
})  

<pre id=O></pre>

Grime v0.1, 31 bytes

E=\0+|\1+
N=.+&E!
e`(E/N|N/E)#!

Imprime 1por partido y 0sin partido.Pruébalo en línea!

Explicación

Grime es mi lenguaje de coincidencia de patrones 2D. Lo modifiqué hoy, pero solo para cambiar el carácter de un elemento de sintaxis (en `lugar de ,), para que no afecte mi puntaje.

Estoy usando un enfoque similar al de Sp3000 : una entrada es falsa si contiene un rectángulo de 2 × N cuya fila contiene ambos 0y 1, y la otra fila no.

E=             Define a nonterminal E, which matches
  \0+|           a horizontal run of one or more 0s, OR
      \1+        a horizontal run of one or more 1s.
N=             Define a nonterminal N, which matches
  .+             a horizontal run of one or more characters,
    &E!          which is NOT matched by E (so contains both 0 and 1).
e`             Match entire input to this pattern:
            !    not
           #     contains
  (E/N|N/E)      E on top of N, or N on top of E

JavaScript (ES6), 64 bytes

s=>(a=s.split`
`).every(l=>l==a[0]|l==a[0].replace(/./g,n=>n^1))

Basado en la observación de @ LevelRiverSt de que cada línea debe ser la misma o la opuesta a la primera.