Advertisement
vfonic

Untitled

Aug 28th, 2014
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cctype>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <vector>
  17.  
  18. #define inf 1000000000
  19. #define MAXN 51
  20.  
  21. using namespace std;
  22.  
  23. int H, W;
  24. char mat[MAXN][MAXN];
  25. int sol_mat[MAXN][MAXN];
  26.  
  27. int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
  28. int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
  29.  
  30. int dfs(int row, int col, char letter) {
  31.     if (sol_mat[row][col] != -1) return sol_mat[row][col];
  32.  
  33.     int curr_pos_sol = 1;
  34.     for (int i = 0; i < 8; ++i) {
  35.         if (row+dx[i] < 0 || row+dx[i] >= H || col+dy[i] < 0 || col+dy[i] >= W) continue;
  36.  
  37.         if (mat[row+dx[i]][col+dy[i]] == letter) {
  38.             curr_pos_sol = 1+dfs(row+dx[i], col+dy[i], letter+1);
  39.         }
  40.     }
  41.  
  42.     sol_mat[row][col] = curr_pos_sol;
  43.     return curr_pos_sol;
  44. }
  45.  
  46. int main() {
  47.     int _case = 0;
  48.     while (true) {
  49.         scanf("%d%d", &H, &W);
  50.         if (!H && !W) return 0;
  51.  
  52.         int sol = 0;
  53.         ++_case;
  54.         memset(sol_mat, -1, sizeof sol_mat);
  55.         for (int i = 0; i < H; ++i) {
  56.             scanf("%s", mat[i]);
  57.         }
  58.  
  59.         for (int i = 0; i < H; ++i) {
  60.             for (int j = 0; j < W; ++j) {
  61.                 if (mat[i][j] != 'A') continue;
  62.  
  63.                 int tmp_sol = dfs(i, j, 'A'+1);
  64.                 if (tmp_sol > sol) sol = tmp_sol;
  65.             }
  66.         }
  67.  
  68.         printf("Case %d: %d\n", _case, sol);
  69.     }
  70.    
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement