Advertisement
Guest User

Untitled

a guest
Mar 6th, 2016
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. string s[1005];
  7. int a[1005][1005];
  8.  
  9. int xs[4] = { 0 , +1 , 0 , -1 };
  10. int ys[4] = { +1 , 0 , -1 , 0 };
  11.  
  12. int main()
  13. {
  14.     int n,m,k;
  15.     cin>>n>>m>>k;
  16.    
  17.     for (int i=1 ; i<=n ; i++)
  18.     {    cin>>s[i]; s[i] = "#"+s[i]+"#"; }
  19.    
  20.     for (int i=0 ; i<m+1 ; i++) s[0].push_back('#') , s[n+1].push_back('#');
  21.    
  22.     int ans = 0;
  23.     queue<pair<int,int>> q;
  24.    
  25.     for (int i=0 ;i<k ; i++)
  26.     {
  27.         int x,y; cin>>x>>y;
  28.         s[x][y] = '#';
  29.         q.push( make_pair( x,y ) );
  30.     }
  31.    
  32.     while ( q.empty() == false )
  33.     {
  34.         pair<int,int> p = q.front() ; q.pop();
  35.        
  36.         for (int i=0 ; i<4 ; i++)
  37.         {
  38.             int x = p.first + xs[i] , y = p.second + ys[i];
  39.             if ( s[x][y] != '#' )
  40.             {
  41.                 a[x][y] = a[p.first][p.second] + 1;
  42.                 s[x][y] = '#';
  43.                 ans += a[x][y];
  44.                 q.push( make_pair( x , y ) );
  45.             }
  46.         }
  47.     }
  48.    
  49.     cout<<ans<<"\n";
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement