fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. class node{
  6. public:
  7.   int value,posx,posy,tems;
  8.   node()
  9.   {
  10.   	tems=-1;
  11.   }
  12.  
  13. };
  14.  
  15.  
  16. int main() {
  17.     int n;
  18.     cin>>n;
  19.  
  20.     while(n--)
  21.      {
  22.      	int a,b;
  23.      	cin>>a>>b;
  24.      	int arr[a][b],high=-1,count=a*b,highest_time=0;
  25.  
  26.         queue<node> obs;
  27.  
  28.      	for(int x=0;x<a;x++)
  29.      	 {
  30.      	 	for(int y=0;y<b;y++)
  31.      	 	 {
  32.      	 	 	cin>>arr[x][y];
  33.      	 	 	if(high==-1||arr[x][y]>high)
  34.      	 	 	  high=arr[x][y];
  35.      	 	 }
  36.      	 }
  37.  
  38.      	for(int x=0;x<a;x++)
  39.      	 {
  40.      	 	for(int y=0;y<b;y++)
  41.      	 	 {
  42.      	 	    if(arr[x][y]==high)
  43.      	 	     {
  44.      	 	     	node ob;
  45.      	 	     	ob.tems=0;
  46.      	 	     	ob.posx=x;
  47.      	 	     	ob.posy=y;
  48.      	 	     	obs.push(ob);
  49.      	 	     	count--;
  50.      	 	     }
  51.      	 	 }
  52.      	 }
  53.  
  54.  
  55.  
  56.      	while(!obs.empty())
  57.      	 {  
  58.      	 	if(count==0)
  59.      	 	break;
  60.      	 	int curx,cury,curtems;
  61.      	 	curx=obs.front().posx;
  62.      	 	cury=obs.front().posy;
  63.      	 	curtems=obs.front().tems;
  64.  
  65.      	    if(cury>0&&arr[curx][cury-1]!=high)
  66.      	     {
  67.      	     	count--;
  68.      	     	arr[curx][cury-1]=high;
  69.  
  70.      	     	node ob;
  71.      	     	ob.posx=curx;
  72.      	     	ob.posy=cury-1;
  73.      	     	ob.tems=curtems+1;
  74.  
  75.      	     	obs.push(ob);
  76.  
  77.      	     	if(highest_time==0||ob.tems>highest_time)
  78.      	     	 highest_time=ob.tems;
  79.      	     }
  80.  
  81.      	 	if(cury<b-1&&arr[curx][cury+1]!=high)
  82.      	 	 {
  83.      	 	 	count--;
  84.      	     	arr[curx][cury+1]=high;
  85.  
  86.      	     	node ob;
  87.      	     	ob.posx=curx;
  88.      	     	ob.posy=cury+1;
  89.      	     	ob.tems=curtems+1;
  90.  
  91.      	     	obs.push(ob);
  92.  
  93.      	     	if(highest_time==0||ob.tems>highest_time)
  94.      	     	 highest_time=ob.tems;
  95.      	 	 }
  96.  
  97.      	   if(curx>0&&arr[curx-1][cury]!=high)
  98.      	    {
  99.      	    	count--;
  100.      	     	arr[curx-1][cury]=high;
  101.  
  102.      	     	node ob;
  103.      	     	ob.posx=curx-1;
  104.      	     	ob.posy=cury;
  105.      	     	ob.tems=curtems+1;
  106.  
  107.      	     	obs.push(ob);
  108.  
  109.      	     	if(highest_time==0||ob.tems>highest_time)
  110.      	     	 highest_time=ob.tems;
  111.      	    }
  112.  
  113.      	   if(curx<a-1&&arr[curx+1][cury]!=high)
  114.      	    {
  115.      	    	count--;
  116.      	     	arr[curx+1][cury]=high;
  117.  
  118.      	     	node ob;
  119.      	     	ob.posx=curx+1;
  120.      	     	ob.posy=cury;
  121.      	     	ob.tems=curtems+1;
  122.  
  123.      	     	obs.push(ob);
  124.  
  125.      	     	if(highest_time==0||ob.tems>highest_time)
  126.      	     	 highest_time=ob.tems;
  127.      	    }
  128.  
  129.      	    if(cury>0&&curx>0&&arr[curx-1][cury-1]!=high)
  130.      	     {
  131.      	     	count--;
  132.      	     	arr[curx-1][cury-1]=high;
  133.  
  134.      	     	node ob;
  135.      	     	ob.posx=curx-1;
  136.      	     	ob.posy=cury-1;
  137.      	     	ob.tems=curtems+1;
  138.  
  139.      	     	obs.push(ob);
  140.  
  141.      	     	if(highest_time==0||ob.tems>highest_time)
  142.      	     	 highest_time=ob.tems;
  143.      	     }
  144.  
  145.      	   if(cury<b-1&&curx<a-1&&arr[curx+1][cury+1]!=high)
  146.      	    {
  147.      	    	count--;
  148.      	     	arr[curx+1][cury+1]=high;
  149.  
  150.      	     	node ob;
  151.      	     	ob.posx=curx+1;
  152.      	     	ob.posy=cury+1;
  153.      	     	ob.tems=curtems+1;
  154.  
  155.      	     	obs.push(ob);
  156.  
  157.      	     	if(highest_time==0||ob.tems>highest_time)
  158.      	     	 highest_time=ob.tems;
  159.      	    }
  160.  
  161.      	   if(cury<b-1&&curx>0&&arr[curx-1][cury+1]!=high)
  162.      	    {
  163.      	    	count--;
  164.      	     	arr[curx-1][cury+1]=high;
  165.  
  166.      	     	node ob;
  167.      	     	ob.posx=curx-1;
  168.      	     	ob.posy=cury+1;
  169.      	     	ob.tems=curtems+1;
  170.  
  171.      	     	obs.push(ob);
  172.  
  173.      	     	if(highest_time==0||ob.tems>highest_time)
  174.      	     	 highest_time=ob.tems;
  175.      	    }
  176.  
  177.      	   if(cury>0&&curx<a-1&&arr[curx+1][cury-1]!=high)
  178.      	    {
  179.      	    	count--;
  180.      	     	arr[curx+1][cury-1]=high;
  181.  
  182.      	     	node ob;
  183.      	     	ob.posx=curx+1;
  184.      	     	ob.posy=cury-1;
  185.      	     	ob.tems=curtems+1;
  186.  
  187.      	     	obs.push(ob);
  188.  
  189.      	     	if(highest_time==0||ob.tems>highest_time)
  190.      	     	 highest_time=ob.tems;
  191.      	    }
  192.  
  193.  
  194.  
  195.  
  196.      	 	obs.pop();
  197.  
  198.      	 }
  199.  
  200.  
  201.      	 cout<<highest_time<<endl;
  202.  
  203.      }
  204. 	return 0;
  205. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
2 2
1 1
1 1
2 2
1 1
1 2
3 4
1 2 1 2
1 1 1 2
1 1 2 2
stdout
copy 
0
1
2
https://ideone.com/eCUCy9
language:
C++14 (gcc 8.3)
created:
11 hours 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!