1 | import java.util.ArrayList;
|
2 | import java.util.Random;
|
3 |
|
4 |
|
5 | public class IrrigationTCGen {
|
6 |
|
7 | private static class Source
|
8 | {
|
9 | public int row;
|
10 | public int col;
|
11 | public int capacity;
|
12 |
|
13 | public Source(int row, int col)
|
14 | {
|
15 | this.row = row;
|
16 | this.col = col;
|
17 | this.capacity = 0;
|
18 | }
|
19 | }
|
20 |
|
21 | private static class Point
|
22 | {
|
23 | public int x,y;
|
24 |
|
25 | public Point(int x, int y)
|
26 | {
|
27 | this.x = x;
|
28 | this.y = y;
|
29 | }
|
30 | }
|
31 |
|
32 | static int[][] field;
|
33 |
|
34 | static int dir[][] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
|
35 |
|
36 | public static void main(String[] args)
|
37 | {
|
38 | int M = Integer.parseInt(args[0]);
|
39 | int N = Integer.parseInt(args[1]);
|
40 |
|
41 | Random rand = new Random(System.nanoTime());
|
42 | boolean found = false;
|
43 |
|
44 | while (!found)
|
45 | {
|
46 | field = new int[M][N]; //M == y, N == x
|
47 |
|
48 | int capacityAvail = N*M;
|
49 | int sourceCount = 0;
|
50 |
|
51 | ArrayList<Source> sourceList = new ArrayList<Source>(200);
|
52 | ArrayList<Point> avail = new ArrayList<Point>(N*M);
|
53 |
|
54 | for (int i = 0; i < M; i++)
|
55 | {
|
56 | for (int j = 0; j < N; j++)
|
57 | {
|
58 | avail.add(new Point(j,i));
|
59 | }
|
60 | }
|
61 |
|
62 | while (capacityAvail > 0)
|
63 | {
|
64 | int row = -1;
|
65 | int col = -1;
|
66 |
|
67 | do
|
68 | {
|
69 | int index = rand.nextInt(avail.size());
|
70 | Point p = avail.get(index);
|
71 | avail.remove(index);
|
72 | row = p.y;
|
73 | col = p.x;
|
74 | } while (field[row][col] != 0);
|
75 |
|
76 | sourceCount++;
|
77 | field[row][col] = sourceCount;
|
78 | capacityAvail--;
|
79 |
|
80 | Source source = new Source(row, col);
|
81 |
|
82 | for (int i = 0; i < 4; i++)
|
83 | {
|
84 | int tempRow = row + dir[i][0];
|
85 | int tempCol = col + dir[i][1];
|
86 | while (0 <= tempRow && tempRow < M && 0 <= tempCol && tempCol < N && field[tempRow][tempCol] == 0)
|
87 | {
|
88 | field[tempRow][tempCol] = sourceCount;
|
89 | source.capacity++;
|
90 | capacityAvail--;
|
91 | tempRow += dir[i][0];
|
92 | tempCol += dir[i][1];
|
93 | }
|
94 | }
|
95 | sourceList.add(source);
|
96 | }
|
97 |
|
98 | if (sourceList.size() <= 200) found = true;
|
99 | else continue;
|
100 |
|
101 | if (found)
|
102 | {
|
103 | System.out.printf("%d %d %d\n", N, M, sourceList.size());
|
104 | for (Source s : sourceList)
|
105 | {
|
106 | System.out.printf("%d %d %d\n", s.col+1, s.row+1, s.capacity);
|
107 | }
|
108 | System.out.printf("0\n");
|
109 | }
|
110 |
|
111 | /*for (int[] row : field)
|
112 | {
|
113 | for (int col : row)
|
114 | {
|
115 | System.out.printf("%02X ", col);
|
116 | }
|
117 | System.out.println();
|
118 | }*/
|
119 | }
|
120 | }
|
121 | }
|