Advertisement
Guest User

castel3

a guest
Feb 22nd, 2020
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. #define MAX_N 180
  7. #define FIN "castel.in"
  8. #define FOUT "castel.out"
  9.  
  10. const int di[] = {-1,+1, 0, 0};
  11. const int dj[] = { 0, 0,-1,+1};
  12.  
  13. int N, M, K, A[MAX_N][MAX_N], Q[MAX_N*MAX_N], Res;
  14. char U[MAX_N][MAX_N], key[MAX_N*MAX_N];
  15. vector<int> key_list[MAX_N*MAX_N];
  16.  
  17. int main(void)
  18. {
  19.     int n, i, j, d, ii, jj, ql, qr;
  20.     vector<int>::iterator it;
  21.  
  22.     freopen(FIN, "r", stdin);
  23.     freopen(FOUT, "w", stdout);
  24.  
  25.     scanf("%d %d %d", &N, &M, &K);
  26.     for (i = 0; i < N; i++)
  27.         for (j = 0; j < M; j++)
  28.         {
  29.             scanf("%d", A[i]+j);
  30.             A[i][j]--;
  31.         }
  32.  
  33.     Q[ql = qr = 0] = --K;
  34.     U[K/M][K%M] = 1;
  35.     for (; ql <= qr; ql++)
  36.     {
  37.         // am cheia N
  38.         key[n = Q[ql]] = 1; Res++;
  39.         for (it = key_list[n].begin(); it != key_list[n].end(); it++)
  40.             if (!U[*it/M][*it%M])
  41.             {
  42.                 Q[++qr] = *it;
  43.                 U[*it/M][*it%M] = 1;
  44.             }
  45.         i = n/M; j = n%M;
  46.         for (d = 0; d < 4; d++)
  47.         {
  48.             ii = i+di[d], jj = j+dj[d];
  49.             if (ii < 0 || jj < 0 || ii >= N || jj >= M || U[ii][jj]) continue;
  50.             if (key[A[ii][jj]])
  51.             {
  52.                 Q[++qr] = ii*M+jj;
  53.                 U[ii][jj] = 1;
  54.             }
  55.             else key_list[A[ii][jj]].push_back(ii*M+jj);
  56.         }
  57.     }
  58.  
  59.     printf("%d\n", Res);
  60.  
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement