fork download
copy 
  1. #define TEMPLATE_VERSION "v0.2 06/03/2019"
  2. #include <bits/stdc++.h>
  3.  
  4. #define MOD (1000000007LL)
  5. #define INF (1000000)
  6. #define LINF (LLONG_MAX)
  7. #define TAM (2019)
  8. #define LL long long int 
  9. #define ULL unsigned long long int
  10. #define LD long double
  11. #define vi vector<int>
  12. #define vb vector<bool>
  13. #define vs vector<string>
  14. #define si set<int>
  15. #define qi queue<int>
  16. #define sti stack<int>
  17. #define vLL vector<LL>
  18. #define pqi priority_queue<int>
  19. #define pii pair<int, int> 
  20. #define vii vector<pii>
  21. #define vvi vector<vi> 
  22. #define vvii vector<vii>
  23. #define vs vector<string>
  24. #define pb push_back
  25. #define mp make_pair
  26. #define f first
  27. #define s second
  28. #define EPS 1e-9
  29. #define loop( n ) for(int i=0; i<n; i++)
  30. #define LOOP(k,n) for(int i=k; i<n; i++)
  31. #define POOL(k,n) for(int i=k; i>=n; i--)
  32. #define FIND(v, value) find(v.begin(), v.end(), value)
  33. #define SORT( v ) sort(v.begin(), v.end())
  34. #define SORTC(v, comp) sort(v.begin(), v.end(), comp)
  35. #define WW( x ) cout<<#x<<" = "<<(x)<<"\n";
  36. #define endl '\n'
  37. using namespace std;
  38.  
  39. vs matriz;
  40. vi pontcomp, minx, miny, maxx, maxy;
  41. vvi comp;
  42. int X, Y, qtde_customers, qtde_offices;
  43.  
  44. void print(){
  45.     loop(X)
  46.         cout << matriz[i] << endl;
  47. }
  48.  
  49.  
  50. struct Customer{
  51.     int x, y, pontos, componente;
  52.     Customer(int a, int b, int c){
  53.         x = a;
  54.         y = b;
  55.         pontos = c;
  56.         componente = 0;
  57.     }
  58. };
  59.  
  60. vector<Customer> customers;
  61.  
  62. int peso(pii pos){
  63.     char op = matriz[pos.f][pos.s];
  64.     if(op=='#') return INF;
  65.     if(op=='~') return 800;
  66.     if(op=='*') return 200;
  67.     if(op=='X') return 120;
  68.     if(op=='_') return 100;
  69.     if(op=='H') return 70;
  70.     if(op=='T') return 50;
  71. }
  72.  
  73. pair<int, string> dijkstra (pii origem, pii destino){
  74.     int dist[TAM][TAM];
  75.     char prev[TAM][TAM];
  76.     for(int i=0; i<TAM; i++)
  77.         for(int j=0; j<TAM; j++)
  78.         {
  79.             dist[i][j] = INF;
  80.             prev[i][j] = 'X';
  81.         }    
  82.     set< pair<int, pii> > fila;
  83.     fila.insert(mp(0, origem));
  84.     dist[origem.f][origem.s] = 0;
  85.     while(!fila.empty()){
  86. 		cout << fila.begin()->second.first << " " << fila.begin()->s.s << "\n";
  87.         pii vertice = fila.begin()->second;
  88.         int distancia = dist[vertice.f][vertice.s];
  89.         int pes = peso(vertice); 
  90.         fila.erase(*fila.begin());
  91.         int moves_x[] = {0, 0, 1, -1};
  92.         int moves_y[] = {1, -1, 0, 0};
  93.         char dir[] = {'R', 'L', 'D', 'U'};
  94.         for(int i=0; i<4; i++){
  95.             int atualX = moves_x[i]+vertice.f;
  96.             int atualY = moves_y[i]+vertice.s;
  97.             if(atualX>=0 and atualX<X and atualY>=0 and atualY<Y){
  98.                 if(dist[atualX][atualY] > distancia + pes){
  99.                     dist[atualX][atualY] = distancia + pes;
  100.                     prev[atualX][atualY] = dir[i];
  101.                     fila.insert(mp(dist[atualX][atualY], mp(atualX, atualY)));
  102.                 }
  103.             }
  104.         }
  105.     }
  106.     string s;
  107.     pii cur = destino;
  108.     while (cur != origem)
  109.     {
  110.         s += prev[cur.f][cur.s];
  111.         if (prev[cur.f][cur.s] == 'U')
  112.             cur.f++;
  113.         else if (prev[cur.f][cur.s] == 'D')
  114.             cur.f--;
  115.         else if (prev[cur.f][cur.s] == 'R')
  116.             cur.s--;
  117.         else if (prev[cur.f][cur.s] == 'L')
  118.             cur.s++;                        
  119.         else
  120.     	{
  121.     		s += 'X';
  122.     		break;
  123.     	}
  124.     }
  125.     string s2 (s.rbegin(), s.rend());
  126.     return mp(dist[destino.f][destino.s], s2);
  127. }
  128.  
  129. bool dfs (int x, int y, int c)
  130. {
  131.     if (x < 0 or x >= X or y < 0 or y >= Y or matriz[x][y] == '#' or comp[x][y] > 0)
  132.         return false;
  133.     comp[x][y] = c;
  134.     dfs(x - 1, y, c);
  135.     dfs(x, y - 1, c);
  136.     dfs(x + 1, y, c);
  137.     dfs(x, y + 1, c);
  138.     return true;
  139. }
  140.  
  141. int init_comp ()
  142. {
  143.     vi aux (Y, 0);
  144.     comp.assign(X, aux);
  145.     int c = 1;
  146.     for (int i = 0; i < X; i++)
  147.         for (int j = 0; j < Y; j++)
  148.             if (dfs(i, j, c))
  149.                 c++;
  150.     pontcomp.assign(c, 0);
  151.     for (int i = 0; i < qtde_customers; i++)
  152.     {
  153.         pontcomp[comp[customers[i].x][customers[i].y]] += customers[i].pontos;
  154.         customers[i].componente = comp[customers[i].x][customers[i].y];
  155.     }
  156.     minx.assign(c, TAM); 
  157.     miny.assign(c, TAM);
  158.     maxx.assign(c, -1);
  159.     maxy.assign(c, -1);
  160.     for (int i = 0; i < X; i++)
  161.         for (int j = 0; j < Y; j++)
  162.         {    
  163.             minx[comp[i][j]] = min(minx[comp[i][j]], i);
  164.             miny[comp[i][j]] = min(miny[comp[i][j]], j);
  165.             maxx[comp[i][j]] = max(maxx[comp[i][j]], i);
  166.             maxy[comp[i][j]] = max(maxy[comp[i][j]], j);           
  167.         }
  168.     int cont = 0;
  169.     for (int i : pontcomp)
  170.         if (i > 0)
  171.             cont++;
  172.     return cont;
  173. }
  174.  
  175. /*
  176. pii binary_search (int c)
  177. {
  178.     int minX = minx[c];
  179.     int minY = miny[c];
  180.     int maxY = maxy[c];
  181.     int maxX = maxx[c];
  182.     pii pos = mp((minX+maxX)/2, (minY+maxY)/2);
  183.     while(peso(pos)!=INF){
  184.         
  185.     }
  186.     
  187.     return pos;
  188. }*/
  189.  
  190. int main () {
  191.     ios_base::sync_with_stdio(false);
  192.     cin >> Y >> X >> qtde_customers >> qtde_offices;
  193.  
  194.  
  195.     loop(qtde_customers){
  196.         int a, b, c;
  197.         cin >> a >> b >> c;
  198.         customers.pb(Customer(b, a, c));
  199.     }
  200.  
  201.     loop(X){
  202.         string a;
  203.         cin >> a;
  204.         matriz.pb(a);
  205.     }
  206.  
  207.     cout << init_comp() << endl;
  208.     print();
  209.  
  210.     int px, py, qx, qy;
  211.     while (cin >> px >> py >> qx >> qy)
  212.     {
  213.     	auto p = dijkstra(mp(px, py), mp(qx, qy));
  214.     	cout << p.f << " " << p.s << "\n";
  215.     }
  216.  
  217.   return 0;
  218. }
Success #stdin #stdout 0.02s 35032KB
comments (?)
stdin
copy 
20 11 4 2 15 1 1700 14 6 1200 3 8 1100 17 9 1050 #################### ##_____T____##___### ####___X_#_______### ######_T_##______### #___TXTT~~##__++__## #___T_#~~~~##+++++_# ____T_#~~~~~#++++___ #______~~~~##+++___# #_______~~#________# ___HHHH*HH*HHHHH*___ ###__________#######
9 7 3 4
0 1 2 2
8 7 5 4
1 0 7 9
0 0 1 1
0 1 1 0
stdout
copy 
1
####################
##_____T____##___###
####___X_#_______###
######_T_##______###
#___TXTT~~##__++__##
#___T_#~~~~##+++++_#
____T_#~~~~~#++++___
#______~~~~##+++___#
#_______~~#________#
___HHHH*HH*HHHHH*___
###__________#######
9 7
8 7
9 6
9 8
10 7
8 6
8 8
9 5
9 9
10 6
10 8
7 7
8 6
8 8
8 5
8 9
9 4
9 10
10 5
10 9
7 6
8 5
8 4
9 3
10 4
7 5
8 4
10 10
6 6
8 3
9 2
10 3
7 4
8 3
6 5
8 10
9 11
10 10
10 11
7 3
8 2
9 1
10 2
6 4
8 11
9 12
5 5
10 12
5 4
6 3
6 3
7 2
8 1
8 12
9 0
9 13
10 1
4 4
5 3
7 11
8 12
4 5
5 6
10 13
8 13
9 14
3 4
4 3
6 2
7 1
7 12
8 0
8 13
10 0
5 2
8 14
9 15
10 14
7 13
8 14
3 3
3 5
4 2
4 6
6 1
7 0
8 15
9 16
10 15
6 13
7 14
3 6
4 7
5 1
7 14
8 15
5 13
6 12
6 14
7 15
3 2
3 7
4 1
4 8
5 7
6 0
4 13
5 12
5 14
6 15
7 16
7 15
8 16
2 6
2 7
3 7
3 8
5 0
4 14
5 15
6 16
3 1
4 0
3 14
4 15
5 16
6 17
7 8
8 9
3 13
4 12
4 14
7 17
8 17
9 17
10 16
6 7
3 15
4 16
5 17
1 6
2 5
2 8
3 9
1 7
2 8
7 9
8 10
4 17
5 18
2 14
3 15
6 18
2 13
3 12
4 11
7 18
0 7
1 8
8 18
9 18
10 17
2 15
3 16
4 17
0 6
1 5
1 8
2 4
2 9
3 17
4 18
5 19
1 14
6 19
1 13
2 12
3 11
7 19
0 8
1 9
8 19
9 19
10 18
1 15
2 16
0 5
1 4
2 3
0 14
1 12
2 11
3 10
0 9
1 10
10 19
0 15
1 16
2 17
0 4
1 3
1 11
2 10
0 10
0 16
1 17
0 3
1 2
0 11
0 2
1 1
2 2
4 9
5 8
6 8
6 9
7 10
4 10
5 9
6 10
5 10
6 11
5 11
760 LLLUUUUUU
0 1
1000000 XX
8 7
7 7
8 6
8 8
9 7
7 6
8 5
9 6
9 5
10 6
6 6
7 5
8 4
9 5
9 8
10 7
9 4
10 5
9 9
10 8
6 5
7 4
8 3
9 3
10 4
8 9
9 10
10 9
9 2
10 3
5 5
6 4
7 3
8 2
10 10
5 4
6 3
9 1
10 2
4 4
4 5
5 3
5 4
5 6
7 2
8 1
8 10
9 11
10 10
10 11
3 4
4 3
6 2
9 0
10 1
5 2
7 1
8 0
8 11
9 12
3 5
4 6
10 12
3 3
4 2
6 1
3 6
4 7
8 12
9 13
10 0
5 1
7 0
7 11
8 12
3 7
4 8
5 7
10 13
3 2
4 1
6 0
8 13
9 14
2 6
2 7
3 7
3 8
7 12
8 13
5 0
6 7
7 6
7 8
8 9
9 8
8 14
9 15
10 14
3 1
4 0
7 13
8 14
1 6
2 5
2 8
3 9
1 7
2 8
8 15
9 16
10 15
6 13
7 14
7 14
8 15
5 13
6 12
6 14
7 15
0 7
1 8
0 6
1 5
1 8
2 4
2 9
4 13
5 12
5 14
6 15
7 16
7 15
8 16
4 14
5 15
6 16
0 8
1 9
3 14
4 15
5 16
6 17
0 5
1 4
2 3
3 13
4 12
4 14
7 17
8 17
9 17
10 16
3 15
4 16
5 17
0 9
1 10
7 9
8 10
4 17
5 18
2 14
3 15
6 18
0 4
1 3
2 13
3 12
4 11
7 18
8 18
9 18
10 17
2 15
3 16
4 17
0 10
1 11
2 10
3 17
4 18
5 19
1 14
6 19
0 3
1 2
1 13
2 12
3 11
7 19
8 19
9 19
10 18
1 15
2 16
0 11
1 12
2 11
3 10
0 14
0 2
1 1
2 2
10 19
0 15
1 16
2 17
0 16
1 17
4 9
5 8
6 8
6 9
7 10
4 10
5 9
6 10
5 10
6 11
5 11
550 LULULU
1 0
1000000 XX
0 0
1000000 XX
0 1
1000000 XX
https://ideone.com/obWGSb
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!