GastonFontenla

Rayuela literaria

Oct 2nd, 2016
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <map>
  5.  
  6. #define a1 (a+x[i])
  7. #define b1 (b+y[i])
  8.  
  9. using namespace std;
  10.  
  11. int x[] = {1, 0, -1, 0};
  12. int y[] = {0, 1, 0, -1};
  13.  
  14. struct Grafo
  15. {
  16.     vector <vector <int> > adj;
  17.     vector <vector <char> > letra;
  18.     int tam, cant;
  19.  
  20.     bool valido(int a, int b)
  21.     {
  22.         return (0 <= a && a < tam && 0 <= b && b < tam);
  23.     }
  24.  
  25.     int maximo;
  26.  
  27.     string s;
  28.  
  29.     void floodfill(int a, int b, int pos, int puntaje)
  30.     {
  31.         if(pos == s.size())
  32.         {
  33.             maximo = max(maximo, puntaje);
  34.             return;
  35.         }
  36.  
  37.         for(int i=0; i<4; i++)
  38.             if(valido(a1, b1) && letra[a1][b1] == s[pos])
  39.                 floodfill(a1, b1, pos+1, puntaje+adj[a1][b1]);
  40.     }
  41.  
  42.     void leer(istream &in, ostream &out)
  43.     {
  44.         in >> tam >> cant;
  45.         adj = vector <vector <int> > (tam, vector <int> (tam));
  46.         letra = vector <vector <char> > (tam, vector <char> (tam));
  47.  
  48.         vector <vector <pair<int, int> > > inicios(300);
  49.  
  50.         for(int i=0; i<tam; i++)
  51.         {
  52.             for(int j=0; j<tam; j++)
  53.             {
  54.                 in >> letra[i][j] >> adj[i][j];
  55.                 inicios[letra[i][j]].push_back(make_pair(i, j));
  56.             }
  57.         }
  58.  
  59.         for(int i=0; i<cant; i++)
  60.         {
  61.             in >> s;
  62.  
  63.             maximo = 0;
  64.             for(int j=0; j<inicios[s[0]].size(); j++)
  65.             {
  66.                 int pos = 1;
  67.                 int px = inicios[s[0]][j].first;
  68.                 int py = inicios[s[0]][j].second;
  69.                 int val = adj[px][py];
  70.  
  71.                 floodfill(px, py, pos, val);
  72.             }
  73.  
  74.             out << maximo << endl;
  75.         }
  76.     }
  77. };
  78.  
  79. int main()
  80. {
  81.     Grafo g;
  82.     g.leer(cin, cout);
  83.  
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment