//testing Ai code
#include "worldmap.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
// Build adjacency list
vector<set<int>> adj(N + 1);
for (int i = 0; i < M; i++) {
adj[A[i]].insert(B[i]);
adj[B[i]].insert(A[i]);
}
// Special case: No edges - just place all countries in a line
if (M == 0) {
vector<vector<int>> C(1, vector<int>(N));
for (int i = 0; i < N; i++) {
C[0][i] = i + 1;
}
return C;
}
// General strategy: Create a cross pattern for each country
// Each country occupies a + shape, allowing edges in 4 directions
// Grid size: 3N x 3N (each country gets a 3x3 region, uses center + 4 arms)
int K = 3 * N;
K = min(K, 240);
vector<vector<int>> C(K, vector<int>(K, 0));
// Assign each country i to position (3*i, 3*i) in a cross pattern
for (int i = 1; i <= N; i++) {
int base_r = (i - 1) * 3;
int base_c = (i - 1) * 3;
if (base_r + 2 < K && base_c + 2 < K) {
// Create a cross pattern
C[base_r + 1][base_c] = i; // Top
C[base_r][base_c + 1] = i; // Left
C[base_r + 1][base_c + 1] = i; // Center
C[base_r + 2][base_c + 1] = i; // Right
C[base_r + 1][base_c + 2] = i; // Bottom
}
}
// Fill remaining cells with country 1 (to ensure no empty cells)
for (int r = 0; r < K; r++) {
for (int c = 0; c < K; c++) {
if (C[r][c] == 0) {
C[r][c] = 1;
}
}
}
// Create edges by connecting adjacent countries
for (int e = 0; e < M; e++) {
int u = A[e];
int v = B[e];
int base_u_r = (u - 1) * 3 + 1;
int base_u_c = (u - 1) * 3 + 1;
int base_v_r = (v - 1) * 3 + 1;
int base_v_c = (v - 1) * 3 + 1;
// Connect u and v by extending arms toward each other
if (base_u_r < base_v_r && base_u_c < K - 1) {
// u is above v, extend u downward
C[base_u_r + 1][base_u_c] = u;
if (base_u_r + 2 < K) C[base_u_r + 2][base_u_c] = v;
} else if (base_u_r > base_v_r && base_u_r > 0) {
// u is below v, extend u upward
C[base_u_r - 1][base_u_c] = u;
if (base_u_r - 2 >= 0) C[base_u_r - 2][base_u_c] = v;
}
if (base_u_c < base_v_c && base_u_r < K - 1) {
// u is left of v, extend u rightward
C[base_u_r][base_u_c + 1] = u;
if (base_u_c + 2 < K) C[base_u_r][base_u_c + 2] = v;
} else if (base_u_c > base_v_c && base_u_c > 0) {
// u is right of v, extend u leftward
C[base_u_r][base_u_c - 1] = u;
if (base_u_c - 2 >= 0) C[base_u_r][base_u_c - 2] = v;
}
}
// Optimization for better K/N ratio: Try smaller grid
if (N <= 10) {
// For small N, try a more compact 2D arrangement
K = N + M / N + 2;
K = max(K, 2);
K = min(K, 240);
C.assign(K, vector<int>(K, 1));
// Place countries in a spiral or grid pattern
int r = 0, c = 0;
for (int i = 1; i <= N; i++) {
if (c < K) {
C[r][c] = i;
c++;
if (c >= K) {
c = 0;
r++;
}
}
}
// Add adjacencies
for (int e = 0; e < M; e++) {
int u = A[e];
int v = B[e];
bool found = false;
// Find where u is and place v adjacent
for (int i = 0; i < K && !found; i++) {
for (int j = 0; j < K && !found; j++) {
if (C[i][j] == u) {
// Try to place v adjacent
if (i + 1 < K && (C[i + 1][j] == 1 || C[i + 1][j] == v)) {
C[i + 1][j] = v;
found = true;
} else if (j + 1 < K && (C[i][j + 1] == 1 || C[i][j + 1] == v)) {
C[i][j + 1] = v;
found = true;
}
}
}
}
}
}
return C;
}
