forked from PlacementPrep100/Graphs
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ConnnectedHorses.java
155 lines (136 loc) · 3.22 KB
/
ConnnectedHorses.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// Connected Horses - HackerEarth
import java.io.*;
import java.util.*;
public class ConnnectedHorses {
static class Pair {
int x, y;
Pair(int x1, int y1) {
x = x1; y = y1;
}
}
static int [][]dirs = {{ -2, 1}, {2, -1}, { -1, -2}, { -1, 2}, {1, 2}, {1, -2}, { -2, -1}, {2, 1}};
static int [][]graph;
static int n, m;
static int mod = (int)(1e9 + 7);
static long []fact;
static int solver() {
boolean [][]visited = new boolean[n + 1][m + 1];
long res = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && graph[i][j] == 1) {
int len = bfs(i, j, visited);
res = (res % mod * fact[len] % mod) % mod;
}
}
}
return (int)res;
}
static int bfs(int x, int y, boolean [][]visited) {
visited[x][y] = true;
int len = 1;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(x, y));
while (!q.isEmpty()) {
Pair curr = q.poll();
int i = curr.x, j = curr.y;
for (int []dir : dirs) {
int x1 = i + dir[0], y1 = j + dir[1];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !visited[x1][y1] && graph[x1][y1] == 1) {
visited[x1][y1] = true;
len++;
q.add(new Pair(x1, y1));
}
}
}
return len;
}
public static void main(String[] args)throws IOException {
InputReader in = new InputReader();
PrintWriter pw = new PrintWriter(System.out);
fact = new long[1000000 + 1];
fact[0] = 1;
for (int i = 1; i < 1000000; i++)
fact[i] = (fact[i - 1] * i) % mod;
int t = in.nextInt();
while (t-- > 0) {
n = in.nextInt(); m = in.nextInt();
int q = in.nextInt();
int [][]pos = in.read2dArray(q, 2);
graph = new int[n][m];
for (int []p : pos)
graph[p[0] - 1][p[1] - 1] = 1;
System.out.println(solver());
}
pw.close();
}
static final Random random = new Random();
static void ruffleSort(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int oi = random.nextInt(n), temp = a[oi];
a[oi] = a[i];
a[i] = temp;
}
ArrayList<Integer> lst = new ArrayList<>();
for (int i : a)
lst.add(i);
Collections.sort(lst);
for (int i = 0; i < n; i++)
a[i] = lst.get(i);
}
static class InputReader {
BufferedReader br;
StringTokenizer st;
public InputReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
int[] readArray(int n) {
int []a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
long[] readLongArray(int n) {
long []a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
int [][] read2dArray(int n, int m) {
int [][]a = new int[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
a[i][j] = nextInt();
return a;
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}