Encuentra las coordenadas del cuarto vértice de un rectángulo con 3 vértices dados

Dada una cuadrícula N * M. Contiene exactamente tres ‘*’ y cada otra celda es un ‘.’ donde ‘*’ denota un vértice de un rectángulo. La tarea es encontrar las coordenadas del cuarto vértice (faltante) (indexación basada en 1).
Ejemplos: 
 

Entrada: grid[][] = {“*.*”, “*..”, “…”} 
Salida: 2 3 
(1, 1), (1, 3) y (2, 1) son las coordenadas dadas del rectángulo donde (2, 3) es la coordenada faltante.
Entrada: grid[][] = {“*.*”, “..*”} 
Salida: 2 1 
 

Enfoque: encuentre las coordenadas de los 3 vértices iterando a través de la cuadrícula dada. Dado que un rectángulo consta de 2 coordenadas X, 2 coordenadas Y y 4 vértices, cada coordenada X y cada coordenada Y deben aparecer exactamente dos veces. Podemos contar cuántas veces ocurre cada coordenada X e Y en los 3 vértices dados y el 4º tendrá coordenadas que ocurren solo una vez.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that return the coordinates
// of the fourth vertex of the rectangle
pair<int, int> findFourthVertex(int n, int m, string s[])
{
    unordered_map<int, int> row, col;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
 
            // Save the coordinates of the given
            // vertices of the rectangle
            if (s[i][j] == '*') {
                row[i]++;
                col[j]++;
            }
    int x, y;
    for (auto tm : row)
        if (tm.second == 1)
            x = tm.first;
    for (auto tm : col)
        if (tm.second == 1)
            y = tm.first;
 
    // 1-based indexing
    return make_pair(x + 1, y + 1);
}
 
// Driver code
int main()
{
    string s[] = { "*.*", "*..", "..." };
    int n = sizeof(s) / sizeof(s[0]);
    int m = s[0].length();
 
    auto rs = findFourthVertex(n, m, s);
    cout << rs.first << " " << rs.second;
}

// Java implementation of the approach
import java.util.HashMap;
import java.util.Map;
 
class GfG
{
 
    // Function that return the coordinates
    // of the fourth vertex of the rectangle
    static Pair<Integer, Integer> findFourthVertex(int n,
                                        int m, String s[])
    {
        HashMap<Integer, Integer> row = new HashMap<>();
        HashMap<Integer, Integer> col = new HashMap<>();
         
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
     
                // Save the coordinates of the given
                // vertices of the rectangle
                if (s[i].charAt(j) == '*')
                {
                     
                    if (row.containsKey(i))
                    {
                        row.put(i, row.get(i) + 1);
                    }
                    else
                    {
                        row.put(i, 1);
                    }
                     
                    if (col.containsKey(j))
                    {
                        col.put(j, col.get(j) + 1);
                    }
                    else
                    {
                        col.put(j, 1);
                    }
                }
            }
        }
                 
        int x = 0, y = 0;
        for (Map.Entry<Integer, Integer> entry : row.entrySet())
        {
            if (entry.getValue() == 1)
                x = entry.getKey();
        }
                 
        for (Map.Entry<Integer, Integer> entry : col.entrySet())
        {
            if (entry.getValue() == 1)
                y = entry.getKey();
        }
     
        // 1-based indexing
        Pair<Integer, Integer> ans = new Pair<>(x + 1, y + 1);
        return ans;
    }
 
    // Driver Code
    public static void main(String []args)
    {
         
        String s[] = { "*.*", "*..", "..." };
        int n = s.length;
        int m = s[0].length();
     
        Pair<Integer, Integer> rs = findFourthVertex(n, m, s);
        System.out.println(rs.first + " " + rs.second);
    }
}
 
class Pair<A, B>
{
    A first;
    B second;
 
    public Pair(A first, B second)
    {
        this.first = first;
        this.second = second;
    }
}
     
// This code is contributed by Rituraj Jain

# Python3 implementation of the approach
 
# Function that return the coordinates
# of the fourth vertex of the rectangle
def findFourthVertex(n, m, s) :
 
    row = dict.fromkeys(range(n), 0)
    col = dict.fromkeys(range(m), 0)
     
    for i in range(n) :
        for j in range(m) :
 
            # Save the coordinates of the given
            # vertices of the rectangle
            if (s[i][j] == '*') :
                row[i] += 1;
                col[j] += 1;
 
    for keys,values in row.items() :
        if (values == 1) :
            x = keys;
             
    for keys,values in col.items() :
        if (values == 1) :
            y = keys;
 
    # 1-based indexing
    return (x + 1, y + 1) ;
 
# Driver code
if __name__ == "__main__" :
     
    s = [ "*.*", "*..", "..." ]
    n = len(s);
    m = len(s[0]);
     
    rs = findFourthVertex(n, m, s);
    print(rs[0], rs[1])
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GfG
{
 
    // Function that return the coordinates
    // of the fourth vertex of the rectangle
    static Pair<int, int> findFourthVertex(int n,
                                        int m, String []s)
    {
        Dictionary<int, int> row = new Dictionary<int, int>();
        Dictionary<int, int> col = new Dictionary<int, int>();
         
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
     
                // Save the coordinates of the given
                // vertices of the rectangle
                if (s[i][j] == '*')
                {
                     
                    if (row.ContainsKey(i))
                    {
                        row[i] = row[i] + 1;
                    }
                    else
                    {
                        row.Add(i, 1);
                    }
                     
                    if (col.ContainsKey(j))
                    {
                        col[j] = col[j] + 1;
                    }
                    else
                    {
                        col.Add(j, 1);
                    }
                }
            }
        }
                 
        int x = 0, y = 0;
        foreach(KeyValuePair<int, int> entry in row)
        {
            if (entry.Value == 1)
                x = entry.Key;
        }
                 
        foreach(KeyValuePair<int, int> entry in col)
        {
            if (entry.Value == 1)
                y = entry.Key;
        }
     
        // 1-based indexing
        Pair<int, int> ans = new Pair<int, int>(x + 1, y + 1);
        return ans;
    }
 
    // Driver Code
    public static void Main(String []args)
    {
         
        String []s = { "*.*", "*..", "..." };
        int n = s.Length;
        int m = s[0].Length;
     
        Pair<int, int> rs = findFourthVertex(n, m, s);
        Console.WriteLine(rs.first + " " + rs.second);
    }
}
 
class Pair<A, B>
{
    public A first;
    public B second;
 
    public Pair(A first, B second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function that return the coordinates
// of the fourth vertex of the rectangle
function findFourthVertex(n, m, s)
{
    var row = new Map(), col = new Map();
    for (var i = 0; i < n; i++)
        for (var j = 0; j < m; j++)
 
            // Save the coordinates of the given
            // vertices of the rectangle
            if (s[i][j] == '*') {
 
                if(row.has(i))
                    row.set(i, row.get(i)+1)
                else
                    row.set(i, 1)
 
                if(col.has(j))
                    col.set(j, col.get(j)+1)
                else
                    col.set(j, 1)
            }
    var x, y;
    row.forEach((value, key) => {
        if (value == 1)
            x = key;
    });
 
    col.forEach((value, key) => {
        if (value == 1)
            y = key;
    });
     
    // 1-based indexing
    return [x + 1, y + 1];
}
 
// Driver code
var s = ["*.*", "*..", "..." ];
var n = s.length;
var m = s[0].length;
var rs = findFourthVertex(n, m, s);
document.write( rs[0] + " " + rs[1]);
 
// This code is contributed by famously.
</script>

2 3

Complejidad de tiempo: O(N*M), ya que estamos usando un bucle para atravesar N*M veces.
 Espacio auxiliar: O(N + M), ya que estamos usando espacio adicional para el mapa.