fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<stack>
  5. #include<algorithm>
  6. #include<queue>
  7. #define gc getchar
  8. #define ll long long
  9.  
  10.  
  11. //typedef unsigned long long int uint;
  12. //typedef long long int64;
  13. //typedef unsigned long long uint64;
  14. using namespace std;
  15. struct node
  16. {
  17.  
  18.     vector<int> neb;
  19.     int dist;
  20.     int nn;
  21.     int val;
  22.     int col;
  23.     int ans;
  24. } ar[100001];
  25.  int arr[190][190];
  26.  int arr1[190][190];
  27. void connect(int a,int b,int i,int j)
  28. {
  29.     ar[a].neb.push_back(b);
  30.     ar[b].neb.push_back(a);
  31.     ar[a].nn++;
  32.     ar[b].nn++;
  33.     ar[a].val=arr[i][j];
  34. }
  35. vector<int> one;
  36. void bfs(int v,int k)
  37. {
  38.    queue<int> myqueue;
  39.    for(int i=1;i<=k;i++)
  40.    {
  41.    	if(i!=v)
  42.    	{
  43.    	ar[i].col=1;
  44.    	ar[i].dist=0;
  45.    	}
  46.    }	
  47.   ar[v].col=2;
  48.   ar[v].dist=0;
  49.   myqueue.push(v);
  50.   int min=0;
  51.   bool fi=true;
  52.   while(!myqueue.empty())
  53.   {
  54.   	int curr=myqueue.front();
  55.   	myqueue.pop();
  56.   	//cout << curr << " " << ar[curr].dist << endl;
  57.  
  58.   	for(int i=0;i<ar[curr].nn;i++)
  59.   	{
  60.   		//cout << ar[curr].neb[i]<< " ";
  61.   	 	if(ar[ar[curr].neb[i]].col==1 && (ar[ar[curr].neb[i]].val)==1)
  62.   	 	  {
  63.   	 	      ar[ar[curr].neb[i]].dist=0;
  64.   	 	      ar[ar[curr].neb[i]].col=2;
  65.   	 	      myqueue.push(ar[curr].neb[i]);
  66.   	 	  }
  67.   	    else if(ar[ar[curr].neb[i]].val==0 && ar[ar[curr].neb[i]].dist==0)
  68.   	      {
  69.   	      	ar[ar[curr].neb[i]].dist=ar[curr].dist + 1;
  70.   	      	myqueue.push(ar[curr].neb[i]);
  71.   	      }
  72.   	     else if((ar[curr].dist+1) < ar[ar[curr].neb[i]].dist) 
  73.   	    {
  74.   	      ar[ar[curr].neb[i]].dist=ar[curr].dist + 1;
  75.   	     myqueue.push(ar[curr].neb[i]);
  76.   	    }
  77.   	    //}
  78.   	}
  79.   	//cout << endl;
  80.   	ar[curr].col=3;
  81.   }
  82.  
  83. }
  84. int main()
  85. {
  86. 	int t;
  87. 	cin >> t;
  88. 	while(t-->0)
  89. 	{
  90. 	  int n,m;
  91. 	  cin >> n >> m;
  92. 	  int k=0;
  93. 	  string str[n+1];
  94. 	  for(int i=1;i<=n;i++)
  95. 	     {
  96. 	     	 cin >> str[i];
  97. 	     }
  98. 	     int g;
  99. 	     bool check=true;
  100. 	  for(int i=1;i<=n;i++)
  101. 	     {
  102. 	     	for(int j=1;j<=m;j++)
  103. 	     	{
  104. 	     		k++;
  105. 	     		if(str[i].at(j-1)=='0')
  106. 	     		arr[i][j]=0;
  107. 	     		else
  108. 	     		{
  109. 	     		arr[i][j]=1;
  110. 	     		if(check)
  111. 	     		   g=k;
  112. 	     		  check=false;
  113. 	     		}
  114. 	     		arr1[i][j]=k;
  115. 	     		}
  116. 	     }
  117.  
  118. 	  for(int i=1;i<=n;i++)
  119. 	    {
  120. 	    	for(int j=1;j<=m;j++)
  121. 	           {
  122.  
  123. 	           	if(j==m && i!=n)
  124. 	           	{
  125. 	           		connect(arr1[i][j],arr1[i+1][j],i,j);
  126. 	           	}
  127. 	           	else if(j==m && i==n)
  128. 	           	{
  129. 	           		if(arr[i][j]==1)
  130. 	           		ar[k].val=1;
  131. 	           		else
  132. 	           		ar[k].val=0;
  133. 	           	}
  134. 	           	else if(i==n)
  135. 	           	{
  136. 	           		connect(arr1[i][j],arr1[i][j+1],i,j);
  137. 	           	}
  138. 	           	else
  139. 	           	{
  140. 	           	connect(arr1[i][j],arr1[i][j+1],i,j);
  141. 	           	connect(arr1[i][j],arr1[i+1][j],i,j);
  142. 	           	}
  143. 	          }
  144. 	    }
  145. 	    bfs(g,k);
  146. 	    k=0;
  147. 	   for(int i=1;i<=n;i++)
  148. 	     {
  149. 	     	for(int j=1;j<=m;j++)
  150. 	     	{
  151. 	     		k++;
  152. 	            cout << ar[k].dist << " "  ;
  153. 	         }
  154. 	     cout << endl;
  155. 	     }
  156. 	}
  157. 	//cout << ar[1].nn << endl;
  158. return 0;	
  159. }
Success #stdin #stdout 0s 6844KB
comments (?)
stdin
copy 
1
1 4
0001
stdout
copy 
3 2 1 0
https://ideone.com/WRqpR7
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!