3316410_ac_6407ms_35360k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{
	public static void main(String [] args)
	{
		new Main().run();
	}
	
	final static int [][] mov = new int [4][2];
	
	static
	{
		mov[0][0] = 1;mov[1][0] = -1;mov[2][0] = 0;mov[3][0] = 0;
		mov[0][1] = 0;mov[1][1] = 0;mov[2][1] = 1;mov[3][1] = -1;
	}
	
	class Points implements Comparable <Points>
	{
		int height;
		int x, y;
		
		Points (int _height, int _x, int _y)
		{
			height = _height;
			x = _x;
			y = _y;
		}
		
		public int compareTo(Points that)
		{
			return height - that.height;
		}
	}

	public void run()
	{
		Scanner in = new Scanner (System.in);
		int cas;

		cas = in.nextInt();
		while (cas-- > 0)
		{
			int h, w, d;

			h = in.nextInt();
			w = in.nextInt();
			d = in.nextInt();
			
			int [][] id = new int [h][w];
			int [][] height = new int [h][w];
			Points [] p = new Points [w*h]; 

			for (int i = 0; i < h; i++)
			{
				for (int j = 0; j < w; j++)
				{
					id[i][j] = -1;
					height[i][j] = in.nextInt();
					p[i*w+j] = new Points(height[i][j],i,j);
				}
			}
			
			Arrays.sort(p); 
			
			int ans = 0;
			
			for (int i = w*h-1; i >= 0; i--)
			{
				Points t = p[i];
				
				if (id[t.x][t.y]!=-1)
				{
					continue;
				}
				
				boolean gohigher = false;
				int cnt = 0;
				LinkedList <Integer> que = new LinkedList <Integer> ();
				que.addLast(t.x);
				que.addLast(t.y);
				
				while (!que.isEmpty())
				{
					int x = que.removeFirst();
					int y = que.removeFirst();
					if (id[x][y] != -1)
					{
						continue;
					}
					id[x][y] = i;
					if (height[x][y] == height[t.x][t.y])
					{
						cnt++;
					}
					for (int k = 0; k < 4; k++)
					{
						int tx = x + mov[k][0];
						int ty = y + mov[k][1];
						if (tx < 0 || ty < 0 || tx >= h || ty >= w || height[tx][ty] <= height[t.x][t.y] - d)
						{
							continue;
						}
						if (id[tx][ty] > i)
						{
							gohigher = true;
						}
						if (id[tx][ty] == -1)
						{
							que.addLast(tx);
							que.addLast(ty);
						}
					}
				}
				if (!gohigher)
				{
					ans += cnt;
				}
			}
			System.out.println(ans);
		}
	}
}