Puntos alcanzables en un mapa

PorJosé A. Alonso

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

Definir las funciones

tales que

  • (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,

  • (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Soluciones

5 Comentarios

  1. Responder

  2. Responder

  3. Responder

  4. Responder

  5. #include<bits/stdc++.h>

    using namespace std;

    int distance(pair<int,int> p1, pair<int,int> p2){
    int d=0;
    d=abs(p1.first-p2.first)+abs(p2.first-p2.second);
    return d;
    }

    int main(){

    int r, c;
    cin >> r >> c;
    char mapa[r+2][c+2]={};
    for(int i=1; i<=r; i++){
    for(int j=1; j<=c; j++){
    cin >> mapa[i][j];
    }
    }
    bool visited[r+2][c+2]={};
    for(int i=1; i<=c; i++){
    visited[0][i]=true;
    visited[r+1][i]=true;
    }
    for(int i=1; i<=r; i++){
    visited[i][0]=true;
    visited[i][c+1]=true;
    }
    int regiones[r+2][c+2]={};
    int regN = 1;
    for(int i=1; i<=r; i++){
    for(int j=1; j<=c; j++){
    if(!visited[i][j]){
    queue<pair<int, int> > cola;
    cola.push(make_pair(i,j));
    visited[i][j]=true;
    regiones[i][j]=regN;
    while(!cola.empty()){
    pair<int,int> p;
    p=cola.front();
    cola.pop();
    if(!visited[p.first-1][p.second]&&mapa[i][j]==mapa[p.first-1][p.second]){
    cola.push(make_pair(p.first-1, p.second));
    regiones[p.first-1][p.second]=regN;
    visited[p.first-1][p.second]=true;
    }
    if(!visited[p.first+1][p.second]&&mapa[i][j]==mapa[p.first+1][p.second]){
    cola.push(make_pair(p.first+1, p.second));
    regiones[p.first+1][p.second]=regN;
    visited[p.first+1][p.second]=true;
    }
    if(!visited[p.first][p.second-1]&&mapa[i][j]==mapa[p.first][p.second-1]){
    cola.push(make_pair(p.first, p.second-1));
    regiones[p.first][p.second-1]=regN;
    visited[p.first][p.second-1]=true;
    }
    if(!visited[p.first][p.second+1]&&mapa[i][j]==mapa[p.first][p.second+1]){
    cola.push(make_pair(p.first, p.second+1));
    regiones[p.first][p.second+1]=regN;
    visited[p.first][p.second+1]=true;
    }
    }
    regN++;
    }
    }
    }

    /*
    for(int i=1; i<=r; i++){
    for(int j=1; j<=c; j++){
    cout << regiones[i][j] << " ";
    }
    cout << endl;
    }
    */

    int n;
    cin >> n;
    while(n--){
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if(regiones[x1][y1]==regiones[x2][y2]){
    if(mapa[x1][y1]=='0') cout << "binary" << endl;
    else cout << "decimal" << endl;
    continue;
    }
    cout << "neither" << endl;
    }

    return 0;
    }

    Responder

Escribe tu solución