fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define in freopen("Warecraft tranquilpaths.txt", "r", stdin);
  5. #define out freopen("output.txt", "w", stdout);
  6.  
  7. #define pb push_back
  8. #define ll long long
  9. #define endl '\n'
  10.  
  11. vector<vector<int>> vis ;
  12. vector<vector<char>> grid;
  13. int di[] = {1 , -1 , 0 , 0 , 1 , -1 , -1 , 1};
  14. int dj[] = {0 , 0 , 1 ,-1 , 1 , -1 , 1 , -1};
  15. int n, m, d;
  16. vector<vector<long double>> dis ;
  17. vector<vector<pair<int, int>>> parent;
  18. vector<vector<bool>> added;
  19. void dijkstra(pair<int , int > st , pair<int , int> en, int day){
  20.     // vis[st.first][st.second]=true;
  21.     priority_queue<tuple<long double, int,int>>q ;
  22.     // if(added[st.first][st.second])
  23.     //     q.push(0, st.first , st.second});
  24.     // else
  25.         q.push({0, st.first , st.second});
  26.  
  27.     vis.assign(n, vector<int>(m, false));
  28.     ll const OO = 2e18;
  29.     dis.assign(n, vector<long double>(m, OO));
  30.  
  31.     while(q.size()){
  32.         auto to = q.top();
  33.         auto [cst, i, j] = to;
  34.         q.pop();
  35.         if(vis[i][j]++)continue ;
  36.  
  37.  
  38.         // cout << i << ' ' << j << ' ' << cst << endl;
  39.         if(i == en.first && j == en.second)
  40.             break;
  41.  
  42.         // cout.flush();
  43.         for(int k = 0 ; k < 8 ; k ++){
  44.             int ni = di[k] + i ;
  45.             int nj = dj[k] + j ;
  46.  
  47.             if(ni < 0 || nj < 0 || ni >= n ||  nj >= m || vis[ni][nj] || grid[ni][nj] == '#')
  48.                  continue ;
  49.  
  50.             long double val = (grid[i][j] == 'C' ? 1 : grid[i][j] == 'N' ? 2 : 5);
  51.             if(added[ni][nj] && make_pair(ni, nj) != en)
  52.                 val += 100;
  53.  
  54.             if(k >= 4){
  55.                 if(grid[ni][j] == '#' && grid[i][nj] == '#')
  56.                     continue;
  57.                 // if(i == 43 && j == 74){
  58.                 //     cout << "Here: " << ni << ' ' << nj << endl;
  59.                 // }
  60.                 val *= sqrt(2);
  61.                 // cout << "val: " << val << endl;
  62.             }
  63.  
  64.             if(dis[ni][nj] > val - cst){
  65.                 dis[ni][nj] = val - cst ;
  66.                 q.push({-val + cst, ni,nj});
  67.                 parent[ni][nj] = {i, j};
  68.             }
  69.         }
  70.     }
  71. }
  72.  
  73. void print(int x, int y, int i, int j){
  74. // is
  75.     cout << '(' << y << ',' << x << ')' << ' ';
  76.     added[x][y] = 1;
  77.     if(x == i && y == j)
  78.         return;
  79.     print(parent[x][y].first, parent[x][y].second, i, j);
  80. }
  81.  
  82. void solve(){
  83.  
  84.  
  85.     cin >> n >> m >> d;
  86.  
  87.     // #: 0, C: 1, N: 2, D: 5 
  88.     grid.assign(n, vector<char> (m, -1));
  89.     added.assign(n, vector<bool> (m, 0));
  90.     // vis.assign(n, vector<int> (m, 0));
  91.     // dis.assign(n, vector<long double> (m, 2e18));
  92.     parent.assign(n, vector<pair<int, int>> (m, {-1, -1}));
  93.     vector<pair<int, int>> start(d + 1, {-1, -1}), finish(d + 1, {-1, -1});
  94.     for(int i = 0; i < n; i++){
  95.         for(int j = 0; j < m; j++){
  96.             string cell;
  97.             cin >> cell;
  98.             if(cell.back() == '}'){
  99.                 int curr = 0;
  100.                 for(int k = 2; k < cell.size(); k++){
  101.                     if(cell[k] == ',' || cell[k] == '}'){
  102.                         (start[curr] == make_pair(-1, -1) ? start[curr] : finish[curr]) = {i, j};
  103.                         curr = 0;
  104.                         continue;
  105.                     }
  106.                     curr = curr * 10 + (cell[k] - '0');
  107.                 }
  108.                 grid[i][j] = cell[0];
  109.             }else{
  110.                 if(cell[0] == '#'){
  111.                     grid[i][j] = '#';
  112.                 }else if(cell[0] == 'C'){
  113.                     grid[i][j] = 'C';
  114.                 }else if(cell[0] == 'N'){
  115.                     grid[i][j] = 'N';
  116.                 }else if(cell[0] == 'D'){
  117.                     grid[i][j] = 'D';
  118.                 }else{
  119.                     int x = stoi(cell);
  120.                     (start[x] == make_pair(-1, -1) ? start[x] : finish[x]) = {i, j};
  121.                     grid[i][j] = 'C';
  122.                 }
  123.             }
  124.         }
  125.     }
  126.  
  127.  
  128.     for(int day = 1; day <= d; day++){
  129.         dijkstra(start[day], finish[day], day);
  130.         auto [x, y] = finish[day];
  131.         // cout << dis[x][y] << endl;
  132.         print(x, y, start[day].first, start[day].second);
  133.         cout << endl;
  134.         // if(day == 82){
  135.         //     break;
  136.         // }
  137.     }
  138.  
  139.  
  140.  
  141.  
  142.  
  143. }
  144.  
  145. int32_t main(){
  146.     ios_base::sync_with_stdio(0);
  147.     cin.tie(0);
  148.  
  149.     in;
  150.     out;
  151.  
  152.     int t = 1;
  153.     // cin >> t;
  154.  
  155.     while(t--)
  156.         solve();
  157.  
  158.     return 0;
  159. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GyFPwk
language:
C++ (gcc 8.3)
created:
2 hours 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!