Advertisement
Malinovsky239

Untitled

Mar 22nd, 2012
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <cassert>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <cctype>
  9. #include <string>
  10. #include <ctime>
  11. #include <cmath>
  12. #include <set>
  13. #include <map>
  14.  
  15. typedef long double LD;
  16. typedef long long LL;
  17.  
  18. using namespace std;
  19.  
  20. #define sz(A) (A).size()
  21. #define mp make_pair
  22. #define pb push_back
  23.  
  24. #define N 15
  25. #define M 17
  26. #define x first
  27. #define y second
  28.  
  29. char plan[M][M];
  30. int cnt[M][M], cnt_next[M][M], dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
  31.  
  32. void read() {
  33.     for (int i = 1; i <= N; i++)
  34.         for (int j = 1; j <= N; j++)
  35.             cin >> plan[i][j];
  36.     for (int i = 1; i <= N; i++)
  37.         for (int j = 1; j <= N; j++)
  38.             cin >> cnt[i][j];
  39. }
  40.  
  41. void end_move() {
  42.     cout << endl;
  43.     int trash;
  44.     cin >> trash;  
  45. }
  46.  
  47. int dist[M][M], qx[M * M], qy[M * M], l, r;
  48. pair<int, int> from[M][M];
  49.  
  50. void push(int x, int y) {
  51.     qx[r] = x, qy[r++] = y;
  52. }
  53.  
  54. void print_move(int x1, int y1, int x2, int y2) {
  55.     cout << x1 - 1 << " " << y1 - 1 << " ";
  56.     for (int i = 0; i < 4; i++)
  57.         if (x1 + dx[i] == x2 && y1 + dy[i] == y2) {
  58.             cout << i << " ";
  59.             break;
  60.         }
  61.     cout << cnt[x1][y1] << endl;
  62. }
  63.  
  64. void bfs(int x, int y) {
  65.     l = r = 0;
  66.     push(x, y);
  67.  
  68.     while (l < r) {
  69.         int now_x = qx[l], now_y = qy[l++];
  70.         for (int i = 0; i < 4; i++) {
  71.  
  72.             int to_x = now_x + dx[i], to_y = now_y + dy[i];
  73.  
  74.             if (plan[to_x][to_y] == '#')
  75.                 continue;
  76.  
  77.             if (dist[to_x][to_y])
  78.                 continue;          
  79.  
  80.             if ( (cnt[to_x][to_y] < 0 && -cnt[to_x][to_y] > cnt[x][y]) || (cnt_next[to_x][to_y] < 0 && -cnt_next[to_x][to_y] > cnt[x][y]) )
  81.                 continue;
  82.  
  83.             if (cnt[to_x][to_y] < 0 || plan[to_x][to_y] == '#' || plan[to_x][to_y] == 'H') {
  84.  
  85.                 if (now_x == x && now_y == y) {
  86.                     print_move(x, y, to_x, to_y);
  87.                     return;
  88.                 }
  89.  
  90.                 while (from[now_x][now_y] != mp(x, y)) {
  91.                     int prev_x = now_x;
  92.                     now_x = from[prev_x][now_y].x;
  93.                     now_y = from[prev_x][now_y].y;
  94.                 }
  95.                 print_move(x, y, now_x, now_y);
  96.                 return;
  97.             }
  98.                    
  99.             dist[to_x][to_y] = dist[now_x][now_y] + 1;
  100.             from[to_x][to_y] = mp(now_x, now_y);
  101.             push(to_x, to_y);
  102.         }
  103.     }                                      
  104. }
  105.  
  106. int main() {
  107.     read();
  108.  
  109.     for (int i = 1; i <= N; i++)
  110.         for (int j = 1; j <= N; j++)
  111.             for (int k = 0; k < 4; k++)
  112.                 if (cnt[i + dx[k] ][j + dy[k] ] < 0)
  113.                     cnt_next[i][j] -= cnt[ i + dx[k] ][ j + dy[k] ];                       
  114.                            
  115.     for (int i = 1; i <= N; i++)
  116.         for (int j = 1; j <= N; j++) {
  117.             if (cnt[i][j] > 0) {
  118.                 bfs(i, j);
  119.             }  
  120.         }
  121.  
  122.     end_move();
  123.  
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement