Maruf_Hasan

uva722

Feb 8th, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.95 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define pb push_back
  6. #define ll long long
  7. #define pii pair<int,int>
  8. #define pll pair<ll,ll>
  9. #define M 100007
  10. #define INF 1e9
  11. #define INFL 1e18
  12. #define PI acos(-1)
  13. #define mp make_pair
  14. #define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  15.  
  16. int fx[]= {+1,-1,+0,+0};
  17. int fy[]= {+0,+0,+1,-1};
  18. int cell[110][110];
  19.  
  20. int x,y;
  21. int visited[110][110];
  22. int dis[110][110];
  23.  
  24.  
  25.  
  26. int bfs(int row,int col)
  27. {
  28. memset(visited,0,sizeof visited);
  29. memset(dis,0,sizeof dis);
  30. visited[x][y]=1;
  31. dis[x][y]=0;
  32. queue<pii>q;
  33. int ans=0;
  34. // cout<<row<<" "<<col<<endl;
  35. q.push(mp(x,y));
  36. while(!q.empty())
  37. {
  38. pii u=q.front();
  39. q.pop();
  40. for(int i=0;i<4;i++)
  41. {
  42. int tx=u.first+fx[i];
  43. int ty=u.second+fy[i];
  44. if(tx>=0 && tx<row && ty>=0 && ty<col && cell[tx][ty]!=1 && visited[tx][ty]==0)
  45. {
  46. visited[tx][ty]=1;
  47. dis[tx][ty]=dis[u.first][u.second]+1;
  48. ans++;
  49. q.push(mp(tx,ty));
  50. }
  51. }
  52. }
  53. return ans+1;
  54. }
  55. int main()
  56. {
  57. fast_in_out;
  58. // freopen("722output.txt","w",stdout);
  59. int q;
  60. scanf("%d ",&q);
  61. while(q--)
  62. {
  63.  
  64. //freopen("input.txt","r",stdin);
  65.  
  66. char s[100];
  67. gets(s);
  68. sscanf(s,"%d%d",&x,&y);
  69. string a[100];
  70. int cnt=0;
  71. char str[100];
  72. getchar();
  73. while(gets(str) && strlen(str)>0)
  74. {
  75. a[cnt++]=str;
  76.  
  77. }
  78.  
  79. int row=cnt;
  80. int col=a[0].length();
  81. // cout<<row<<" "<<col<<endl;
  82. memset(cell,0,sizeof cell);
  83. for(int i=0;i<cnt;i++)
  84. {
  85. for(int j=0;j<col;j++)
  86. {
  87. if(a[i][j]=='1')
  88. {
  89. cell[i][j]=1;
  90. }
  91. }
  92. }
  93.  
  94. x--;
  95. y--;
  96. int ans=bfs(row,col);
  97. cout<<ans<<endl;
  98. if(q)
  99. cout<<endl;
  100. }
  101. return 0;
  102.  
  103. }
Advertisement
Add Comment
Please, Sign In to add comment