Advertisement
Guest User

Untitled

a guest
May 30th, 2015
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. pair < int , int > charToWay[200];
  9.  
  10. char grid[105][105];
  11. pair < int , int > way[105][105];
  12. char buf[105];
  13. int r, c;
  14.  
  15. int sumRow[105], sumCol[105];
  16.  
  17. bool visited[105][105];
  18. bool f[105][105];
  19. pair < int , int > nextCell[105][105];
  20.  
  21. void buildPairToWay () {
  22.     charToWay['^'] = make_pair(-1, 0);
  23.     charToWay['>'] = make_pair(0, 1);
  24.     charToWay['v'] = make_pair(1, 0);
  25.     charToWay['<'] = make_pair(0, -1);
  26. }
  27.  
  28. bool inField (int x, int y) {
  29.     return x > -1 && x < r && y > -1 && y < c;
  30. }
  31.  
  32. bool checkBadCell () {
  33.     for (int i = 0; i < r; i++) {
  34.         sumRow[i] = 0;
  35.         for (int j = 0; j < c; j++) {
  36.             if (grid[i][j] != '.')
  37.                 sumRow[i]++;
  38.         }
  39.     }
  40.    
  41.     for (int j = 0; j < c; j++) {
  42.         sumCol[j] = 0;
  43.         for (int i = 0; i < r; i++) {
  44.             if (grid[i][j] != '.')
  45.                 sumCol[j]++;
  46.         }
  47.     }
  48.  
  49.     for (int i = 0; i < r; i++)
  50.         for (int j = 0; j < c; j++)
  51.             if (grid[i][j] != '.' && sumRow[i] == 1 && sumCol[j] == 1)
  52.                 return false;
  53.    
  54.     return true;
  55. }
  56.  
  57. void getNextCell (int sx, int sy) {
  58.     int x = sx, y = sy;
  59.     int wx = way[x][y].first, wy = way[x][y].second;
  60.     x += wx; y += wy;
  61.     while (inField(x, y) && grid[x][y] == '.') {
  62.         x += wx; y += wy;
  63.     }
  64.    
  65.     if (!inField(x, y) ) {
  66.         nextCell[sx][sy] = make_pair(-1, -1);
  67.     } else {
  68.         nextCell[sx][sy] = make_pair(x, y);
  69.     }
  70. }
  71.  
  72. void getArrows () {
  73.     for (int i = 0; i < r; i++)
  74.         for (int j = 0; j < c; j++)
  75.             visited[i][j] = false;
  76.    
  77.     for (int i = 0; i < r; i++)
  78.         for (int j = 0; j < c; j++)
  79.             if (grid[i][j] != '.')
  80.                 way[i][j] = charToWay[grid[i][j]];
  81.    
  82.     for (int i = 0; i < r; i++)
  83.         for (int j = 0; j < c; j++)
  84.             if (grid[i][j] != '.')
  85.                 getNextCell(i, j);
  86. }
  87.  
  88. int checkField (int x, int y) {
  89.     f[x][y] = true;
  90.     while (true) {
  91.         int nx = nextCell[x][y].first;
  92.         int ny = nextCell[x][y].second;
  93.        
  94.         if (nx == -1)
  95.             return 1;
  96.        
  97.         if (f[nx][ny] )
  98.             return 0;
  99.        
  100.         x = nx; y = ny;
  101.         f[x][y] = true;
  102.     }
  103.    
  104.     throw 42;
  105. }
  106.  
  107. void solve () {
  108.     if (checkBadCell() ) {
  109.         printf("IMPOSSIBLE\n");
  110.         return ;
  111.     }
  112.    
  113.     getArrows();
  114.    
  115.     for (int i = 0; i < r; i++) {
  116.         for (int j = 0; j < c; j++) {
  117.             f[i][j] = false;
  118.         }
  119.     }
  120.    
  121.     int ans = 0;
  122.     for (int i = 0; i < r; i++) {
  123.         for (int j = 0; j < c; j++) {
  124.             if (!f[i][j] && grid[i][j] != '.')
  125.                 ans += checkField(i, j);
  126.         }
  127.     }
  128.     printf("%d\n", ans);
  129. }
  130.  
  131. int main () {
  132.     freopen("in", "r", stdin);
  133.     freopen("out", "w", stdout);
  134.    
  135.     buildPairToWay();
  136.    
  137.     int tests;
  138.     scanf("%d\n", &tests);
  139.     for (int t = 0; t < tests; t++) {
  140.         scanf("%d%d\n", &r, &c);
  141.         for (int i = 0; i < r; i++) {
  142.             scanf("%s", buf);
  143.             string s = string(buf);
  144.             for (int j = 0; j < c; j++) {
  145.                 grid[i][j] = s[j];
  146.             }
  147.         }
  148.        
  149.         printf("Case #%d: ", t + 1);
  150.        
  151.         solve();
  152.     }
  153.    
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement