Limpiando el cuarto

Dada una habitación con rejillas cuadradas que tienen ‘*’ y ‘.’ representando células desordenadas y normales respectivamente. Debe averiguar si la habitación se puede limpiar o no. Hay una máquina que te ayuda en esta tarea, pero es capaz de limpiar solo una celda normal. Las celdas desordenadas no se pueden limpiar con la máquina, hasta que haya limpiado la celda normal en su fila o columna. Ahora, vea si la habitación se puede limpiar o no. La entrada es la siguiente: la primera línea contiene  el tamaño de la habitación. Las siguientes n líneas contienen la descripción de cada fila donde la fila[i][j] es ‘ ‘ si está más desordenada que otras es ‘ ‘ si es una celda normal. Ejemplos:

Input : 3
        .**
        .**
        .**
Output :Yes, the room can be cleaned.
        1 1
        2 1
        3 1
Input :4
       ****
       ..*.
       ..*.
       ..*.
Output : house cannot be cleaned.

Enfoque : El número mínimo de celdas puede ser n. Es la única respuesta posible, ya que debe tener un elemento de tipo ‘ ‘ en cada fila y columna diferente. Si una columna en particular y una fila determinada contienen ‘ ‘ en todas las celdas, se sabe que la casa no se puede limpiar. Recorra cada fila y encuentre el ‘ ‘ que se puede usar para la máquina. Use este paso dos veces, verifique cada columna para cada fila y luego verifique cada fila para cada columna. Luego verifique si alguno de los dos da respuesta como n. En caso afirmativo, la casa se puede limpiar, de lo contrario no. Este enfoque nos dará la respuesta mínima requerida. En el primer ejemplo, la máquina limpiará la celda (1, 1), (2, 1), (3, 1) para limpiar toda la habitación. En el segundo ejemplo, cada celda de la  fila tiene ‘‘ y cada celda de la  columna contiene ‘ ‘, por lo tanto, la casa no se puede limpiar. fila no se puede limpiar de ninguna manera. 

// CPP code to find whether
// house can be cleaned or not
#include <bits/stdc++.h>
using namespace std;
 
// Matrix A stores the string
char A[105][105];
 
// ans stores the pair of indices
// to be cleaned by the machine
vector<pair<int, int> > ans;
 
// Function for printing the
// vector of pair
void print()
{
    cout << "Yes, the house can be"
         << " cleaned." << endl;
 
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i].first << " "
             << ans[i].second << endl;
}
 
// Function performing calculations
int solve(int n)
{
    // push every first cell in
    // each row containing '.'
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == '.') {
                ans.push_back(make_pair(i + 1, j + 1));
                break;
            }
        }
    }
 
    // If total number of cells are
    // n then house can be cleaned
    if (ans.size() == n) {
        print();
        return 0;
    }
 
    ans.clear();
 
    // push every first cell in
    // each column containing '.'
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[j][i] == '.') {
                ans.push_back(make_pair(i + 1, j + 1));
                break;
            }
        }
    }
 
    // If total number of cells are
    // n then house can be cleaned
    if (ans.size() == n) {
        print();
        return 0;
    }
    cout << "house cannot be cleaned."
         << endl;
}
 
// Driver function
int main()
{
    int n = 3;
    string s = "";
    s += ".**";
    s += ".**";
    s += ".**";
    int k = 0;
 
    // Loop to insert letters from
    // string to array
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            A[i][j] = s[k++];
    }
    solve(n);
    return 0;
}

# Python3 code to find whether
# house can be cleaned or not
 
# Matrix A stores the string
A = [[0 for i in range(105)] for j in range(105)]
 
# ans stores the pair of indices
# to be cleaned by the machine
ans = []
 
# Function for printing the
# vector of pair
def printt():
     
    print("Yes, the house can be cleaned.")
    for i in range(len(ans)):
        print(ans[i][0], ans[i][1])
         
# Function performing calculations
def solve(n):
    global ans
     
    # push every first cell in
    # each row containing '.'
    for i in range(n):
        for j in range(n):
            if (A[i][j] == '.'):
                ans.append([i + 1, j + 1])
                break
             
    # If total number of cells are
    # n then house can be cleaned
    if (len(ans) == n):
        printt()
        return 0
         
    ans = []
     
    # push every first cell in
    # each column containing '.'
    for i in range(n):
        for j in range(n):
            if (A[j][i] == '.'):
                ans.append([i + 1, j + 1])
                break
             
    # If total number of cells are
    # n then house can be cleaned
    if (len(ans) == n):
        printt()
        return 0
    print("house cannot be cleaned.")
 
# Driver function
n = 3
s = ""
s += ".**"
s += ".**"
s += ".**"
k = 0
 
# Loop to insert letters from
# string to array
for i in range(n):
    for j in range(n):
        A[i][j] = s[k]
        k += 1
 
solve(n)
 
# This code is contributed by shubhamsingh10

Producción:

Yes, the house can be cleaned.
1 1
2 1
3 1

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ² )