#include #define MAXN 256 #define MAXM 256 #define MAXK 32 using namespace std; int n, m; char table[MAXN][MAXM]; int t, k; int ans_score = 1000000000; vector ans_moves; pair robots[MAXK]; int ans_idx; void move_cell(int dir, pair &cell) { if (dir == 1) if (cell.first > 1 && table[cell.first-1][cell.second] != '#') cell.first--; if (dir == 2) if (cell.second < m && table[cell.first][cell.second+1] != '#') cell.second++; if (dir == 3) if (cell.first < n && table[cell.first+1][cell.second] != '#') cell.first++; if (dir == 4) if (cell.second > 1 && table[cell.first][cell.second-1] != '#') cell.second--; } int idx; int calc() { int ans = 0; for (int i = 1; i <= k; i++) for (int j = i+1; j <= k; j++) ans = max(ans, abs(robots[i].first-robots[j].first) + abs(robots[i].second-robots[j].second)); return ans; } void f(int curr_cnt, vector curr_moves) { if (calc() * (n + m) + curr_cnt < ans_score) { ans_score = calc() * (n + m) + curr_cnt; ans_idx = idx; ans_moves = curr_moves; } if (curr_cnt >= 8) return; pair old_robots[MAXK]; for (int i = 1; i <= k; i++) old_robots[i] = robots[i]; for (int i = 1; i <= k; i++) move_cell(1, robots[i]); curr_moves.push_back('N'); f(curr_cnt+1, curr_moves); curr_moves.pop_back(); for (int i = 1; i <= k; i++) robots[i] = old_robots[i]; for (int i = 1; i <= k; i++) move_cell(2, robots[i]); curr_moves.push_back('E'); f(curr_cnt+1, curr_moves); curr_moves.pop_back(); for (int i = 1; i <= k; i++) robots[i] = old_robots[i]; for (int i = 1; i <= k; i++) move_cell(3, robots[i]); curr_moves.push_back('S'); f(curr_cnt+1, curr_moves); curr_moves.pop_back(); for (int i = 1; i <= k; i++) robots[i] = old_robots[i]; for (int i = 1; i <= k; i++) move_cell(4, robots[i]); curr_moves.push_back('W'); f(curr_cnt+1, curr_moves); curr_moves.pop_back(); for (int i = 1; i <= k; i++) robots[i] = old_robots[i]; } int main() { freopen("robots.in", "r", stdin); freopen("robots.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> table[i][j]; cin >> t >> k; for (int i = 1; i <= t; i++) { for (int j = 1; j <= k; j++) cin >> robots[j].first >> robots[j].second; idx = i; vector v; f(0, v); } cout << ans_idx << endl; for (auto i: ans_moves) cout << i; cout << endl; }