Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <map>
- #define a1 (a+x[i])
- #define b1 (b+y[i])
- using namespace std;
- int x[] = {1, 0, -1, 0};
- int y[] = {0, 1, 0, -1};
- struct Grafo
- {
- vector <vector <int> > adj;
- vector <vector <char> > letra;
- int tam, cant;
- bool valido(int a, int b)
- {
- return (0 <= a && a < tam && 0 <= b && b < tam);
- }
- int maximo;
- string s;
- void floodfill(int a, int b, int pos, int puntaje)
- {
- if(pos == s.size())
- {
- maximo = max(maximo, puntaje);
- return;
- }
- for(int i=0; i<4; i++)
- if(valido(a1, b1) && letra[a1][b1] == s[pos])
- floodfill(a1, b1, pos+1, puntaje+adj[a1][b1]);
- }
- void leer(istream &in, ostream &out)
- {
- in >> tam >> cant;
- adj = vector <vector <int> > (tam, vector <int> (tam));
- letra = vector <vector <char> > (tam, vector <char> (tam));
- vector <vector <pair<int, int> > > inicios(300);
- for(int i=0; i<tam; i++)
- {
- for(int j=0; j<tam; j++)
- {
- in >> letra[i][j] >> adj[i][j];
- inicios[letra[i][j]].push_back(make_pair(i, j));
- }
- }
- for(int i=0; i<cant; i++)
- {
- in >> s;
- maximo = 0;
- for(int j=0; j<inicios[s[0]].size(); j++)
- {
- int pos = 1;
- int px = inicios[s[0]][j].first;
- int py = inicios[s[0]][j].second;
- int val = adj[px][py];
- floodfill(px, py, pos, val);
- }
- out << maximo << endl;
- }
- }
- };
- int main()
- {
- Grafo g;
- g.leer(cin, cout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment