fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) (x).begin(), (x).end()
  4. #define rall(x) (x).rbegin(), (x).rend()
  5.  
  6. using namespace std; 
  7.  
  8. typedef long long ll; 
  9. typedef pair<int, int> ii; 
  10.  
  11. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. template<typename T>
  17. void minimize(T& a, const T& b) {
  18. 	if (b < a) a = b; 
  19. }
  20.  
  21. const ll LINF = 1e18; 
  22. const int INF = 1e9;
  23.  
  24. const int N = 2e3 + 5; 
  25.  
  26. int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1}; 
  27. int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};  
  28.  
  29. int n;  
  30. int a[N][N]; 
  31.  
  32. // Ô (x, y) thuộc 1 trong 5 loại: 
  33. // 0: Ô thuộc hàng 1
  34. // 1: Ô thuộc cột n 
  35. // 2: Ô thuộc hàng n
  36. // 3: Ô thuộc cột 1
  37. // 4: Trường hợp còn lại
  38. int getIndex(int x, int y) {
  39. 	if (x == 1) return 0;  
  40. 	if (y == n) return 1; 
  41. 	if (x == n) return 2;  
  42. 	if (y == 1) return 3; 
  43. 	return 4; 
  44. }
  45.  
  46. struct Node {
  47. 	int id; // (0 <= id <= 1) là loại của ô xuất phát	
  48. 	int x, y; // toạ độ của ô đang xét
  49. }; 
  50.  
  51. bool vis[2][N][N];  
  52. bool marked[2][5];
  53.  
  54. bool ok(int x, int y) {
  55. 	return (1 <= x && x <= n && 1 <= y && y <= n);  
  56. }
  57.  
  58. // Có tồn tại đường đi nào từ ô (1, 1) đến ô (n, n) sao cho không được đi qua ô nào có giá trị = val
  59. // Tương đương với check các ô có giá trị = val có tạo thành đường đi rơi vào
  60. // 1 trong 4 trường hợp:
  61. // TH1: xuất phát tại một ô hàng 1 và đi đến một ô hàng n
  62. // TH2: xuất phát tại một ô hàng 1 và đi đến một ô cột 1
  63. // TH3: xuất phát tại một ô cột n và đi đến một ô hàng n
  64. // TH4: xuất phát tại một ô cột n và đi đến một ô cột 1
  65. // mỗi bước được đi 8 hướng 
  66. bool bfs(int val) {
  67. 	if (a[1][1] == val || a[n][n] == val) return false;   
  68.  
  69. 	memset(marked, 0, sizeof marked);  
  70.  
  71. 	for (int id = 0; id < 2; id++) {
  72. 		for (int x = 1; x <= n; x++) {
  73. 			for (int y = 1; y <= n; y++) vis[id][x][y] = false; 
  74. 		}
  75. 	}
  76.  
  77. 	queue<Node> q; 
  78.  
  79. 	// Xét các ô có giá trị val ở hàng 1  
  80. 	for (int y = 1; y <= n; y++) {
  81. 		if (a[1][y] == val) {
  82. 			vis[0][1][y] = true; 
  83. 			q.push({0, 1, y}); 
  84. 		}
  85. 	}
  86.  
  87. 	// Xét các ô có giá trị val ở cột n
  88. 	for (int x = 1; x <= n; x++) {
  89. 		if (a[x][n] == val) {
  90. 			vis[1][x][n] = true; 
  91. 			q.push({1, x, n}); 
  92. 		}
  93. 	}
  94.  
  95. 	while (!q.empty()) {
  96. 		Node u = q.front(); q.pop(); 
  97. 		int id = u.id, x = u.x, y = u.y;   
  98.  
  99. 		for (int i = 0; i < 8; i++) {
  100. 			int nx = x + dx[i], ny = y + dy[i];
  101.  
  102. 			if (!ok(nx, ny)) continue; 
  103.  
  104. 			if (a[nx][ny] == val && !vis[id][nx][ny]) {
  105. 				vis[id][nx][ny] = true; 
  106. 				marked[id][getIndex(nx, ny)] = true;  
  107. 				q.push({id, nx, ny});  
  108. 			}
  109. 		}
  110. 	}
  111.  
  112. 	return (!marked[0][2] && !marked[0][3] && !marked[1][2] && !marked[1][3]); 
  113. }
  114.  
  115. bool check(int val) {
  116. 	return bfs(val);  	
  117. }
  118.  
  119. void solve() {
  120. 	cin >> n; 
  121.  
  122. 	for (int x = 1; x <= n; x++) {
  123. 		for (int y = 1; y <= n; y++) cin >> a[x][y];
  124. 	}
  125.  
  126. 	int mex = -1; 
  127. 	for (int val = 1; val <= n * n + 1; val++) {
  128. 		if (check(val)) {
  129. 			mex = val;   
  130. 			break; 
  131. 		}
  132. 	}
  133.  
  134. 	cout << mex << '\n'; 
  135. }
  136.  
  137. signed main() {
  138. 	ios::sync_with_stdio(false); 
  139. 	cin.tie(nullptr); 
  140. 	int tt; 
  141. 	cin >> tt; 
  142. 	while (tt--) {
  143. 		solve(); 
  144. 	}
  145. }
  146.  
Success #stdin #stdout 0.01s 7684KB
comments (?)
stdin
copy 
2
3
3 1 2
1 3 2
1 1 4
2
2 3
3 4
stdout
copy 
2
1
https://ideone.com/Zg91Rr
language:
C++14 (gcc 8.3)
created:
319 days ago
visibility:
secret

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!