fork download 
  1. // ラベリング処理 Labeling
  2. //
  3. // author: Leonardone @ NEETSDKASU
  4. //
  5. import java.util.*;
  6. import java.lang.*;
  7. import java.io.*;
  8.  
  9. class Ideone
  10. {
  11. 	static int[][] map;
  12. 	static int[] groupLink;
  13. 	static int nextGroupID = 1;
  14. 	static int h, w;
  15.  
  16. 	static int getGroupID(int x, int y) {
  17. 		if (x < 0 | x >= w | y < 0 | y >= h) {
  18. 			return 0;
  19. 		}
  20. 		int g = map[y][x];
  21. 		while (groupLink[g] != g) {
  22. 			g = groupLink[g];
  23. 		}
  24. 		map[y][x] = g;
  25. 		return g;
  26. 	}
  27.  
  28. 	static void setGroupID(int x, int y) {
  29. 		int ga = getGroupID(x - 1, y);
  30. 		int gb = getGroupID(x, y - 1);
  31. 		if (ga == 0 && gb == 0) {
  32. 			map[y][x] = nextGroupID;
  33. 			groupLink[nextGroupID] = nextGroupID;
  34. 			nextGroupID++;
  35. 		} else if (ga == 0) {
  36. 			map[y][x] = gb;
  37. 		} else if (gb == 0) {
  38. 			map[y][x] = ga;
  39. 		} else if (ga < gb) {
  40. 			groupLink[gb] = ga;
  41. 			map[y][x] = ga;
  42. 		} else if (ga > gb) {
  43. 			groupLink[ga] = gb;
  44. 			map[y][x] = gb;
  45. 		}
  46. 	}
  47.  
  48. 	public static void main (String[] args) throws java.lang.Exception
  49. 	{
  50. 		Scanner in = new Scanner(System.in);
  51.  
  52. 		w = in.nextInt();
  53. 		h = in.nextInt();
  54.  
  55. 		map = new int[h][w];
  56. 		groupLink = new int[h * w + 1];
  57.  
  58. 		for (int i = 0; i < h; i++) {
  59. 			String line = in.next();
  60. 			for (int j = 0; j < w; j++) {
  61. 				if (line.charAt(j) == '1') {
  62. 					setGroupID(j, i);
  63. 				}
  64. 				System.out.printf("%02d ", map[i][j]);
  65. 			}
  66. 			System.out.println();
  67. 		}
  68.  
  69. 		System.out.println();
  70. 		System.out.println();
  71.  
  72. 		Map<Integer, Character> groupChar = new HashMap<>();
  73. 		char ch = 'A';
  74.  
  75. 		for (int i = 0; i < h; i++) {
  76. 			for (int j = 0; j < w; j++) {
  77. 				Integer g = getGroupID(j, i);
  78. 				if (g > 0) {
  79. 					if (groupChar.containsKey(g) == false) {
  80. 						groupChar.put(g, ch);
  81. 						ch++;
  82. 					}
  83. 					System.out.print(groupChar.get(g));
  84. 				} else {
  85. 					System.out.print('0');
  86. 				}
  87. 			}
  88. 			System.out.println();
  89. 		}
  90. 	}
  91. }
Success #stdin #stdout 0.16s 321088KB
comments (?)
stdin 
10 10
0000011110
0110100100
0100111100
0111100111
0000010001
0100111011
0111010010
0000011010
0011101010
0000011110
stdout 
00 00 00 00 00 01 01 01 01 00 
00 02 02 00 03 00 00 01 00 00 
00 02 00 00 03 03 03 01 00 00 
00 02 02 02 01 00 00 01 01 01 
00 00 00 00 00 04 00 00 00 01 
00 05 00 00 06 04 04 00 07 01 
00 05 05 05 00 04 00 00 01 00 
00 00 00 00 00 04 04 00 01 00 
00 00 08 08 08 00 04 00 01 00 
00 00 00 00 00 09 04 04 01 00 


00000AAAA0
0AA0A00A00
0A00AAAA00
0AAAA00AAA
00000A000A
0B00AAA0AA
0BBB0A00A0
00000AA0A0
00CCC0A0A0
00000AAAA0
https://ideone.com/nOYgNC
language:
Java (HotSpot 12)
created:
9 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!