#include using namespace std; struct pos { int r, c; pos(int r=0, int c=0): r(r), c(c) {} pos operator+(const pos& p) const { return pos(r+p.r, c+p.c); } pos operator-(const pos& p) const { return pos(r-p.r, c-p.c); } bool operator<(const pos& p) const { return r < p.r || r == p.r && c < p.c; } bool operator==(const pos& p) const { return r == p.r && c == p.c; } }; typedef pair frag_pos; const pos dirs[] = {pos(-1, 0), pos(0, 1), pos(1, 0), pos(0, -1)}; const char *dir_sym = "NESW"; struct fragment { set visited, frontier; map traps; fragment() { visited.insert(pos()); } void show() { pos minpos, maxpos; for (auto p: visited) { minpos = pos(min(minpos.r, p.r), min(minpos.c, p.c)); maxpos = pos(max(maxpos.r, p.r), max(maxpos.c, p.c)); } pos dim = pos(3,3) + maxpos - minpos, offs = pos(1,1) - minpos; vector grid(dim.r, string(dim.c, '#')); for (auto p: visited) grid[p.r+offs.r][p.c+offs.c] = '.'; char sym = 'A'; for (auto t: traps) { pos start = t.first, end = t.second.second; grid[start.r+offs.r][start.c+offs.c] = sym; grid[end.r+offs.r][end.c+offs.c] = sym - 'A' + 'a'; //printf("trap (%d,%d) -> (%d,%d) @ frag %d\n", start.r, start.c, end.r, end.c, t.second.first); ++sym; } grid[offs.r][offs.c] = 'S'; cout << dim.r << " " << dim.c << "\n"; for (auto row: grid) cout << row << "\n"; cout.flush(); } void merge(const fragment &f, pos offset) { for (auto p: f.visited) { frontier.erase(p+offset); visited.insert(p+offset); } for (auto p: f.frontier) if (!visited.count(p+offset)) frontier.insert(p+offset); for (auto t: f.traps) traps[t.first+offset] = t.second; } }; int main(void) { vector fragments; fragments.push_back(fragment()); int cur_frag = 0, new_fragments = 0; pos cur_pos; auto get_surroundings = [&]() { string msg; cin >> msg; auto &frag = fragments[cur_frag]; for (int d = 0; d < 4; ++d) if (msg[d] == '.' && !frag.visited.count(cur_pos + dirs[d])) frag.frontier.insert(cur_pos + dirs[d]); }; auto get_response = [&]() { get_surroundings(); string msg; cin >> msg; if (msg == "trap") { auto &frag = fragments[cur_frag]; if (!frag.traps.count(cur_pos)) { ++new_fragments; frag.traps[cur_pos] = frag_pos(fragments.size(), pos()); } cur_frag = frag.traps[cur_pos].first; cur_pos = frag.traps[cur_pos].second; if (cur_frag >= fragments.size()) fragments.push_back(fragment()); get_surroundings(); } }; auto merge_fragments = [&](int frag1, int frag2, pos offset) { for (auto &frag: fragments) for (auto &t: frag.traps) if (t.second.first == frag2) t.second = frag_pos(frag1, t.second.second + offset); else if (t.second.first > frag2) --t.second.first; if (cur_frag == frag2) { cur_frag = frag1; cur_pos = cur_pos + offset; } else if (cur_frag > frag2) { --cur_frag; } fragments[frag1].merge(fragments[frag2], offset); fragments.erase(fragments.begin() + frag2); new_fragments = 0; }; auto find_merge = [&]() { for (int _frag1 = 0; _frag1 < fragments.size(); ++_frag1) { auto &frag1 = fragments[_frag1]; for (int _frag2 = _frag1+1; _frag2 < fragments.size(); ++_frag2) { auto &frag2 = fragments[_frag2]; if (frag1.traps.size() == 2 && frag2.traps.size() == 2) { merge_fragments(_frag1, _frag2, frag1.traps.begin()->first - frag2.traps.begin()->first); return true; } for (auto &t1: frag1.traps) for (auto &t2: frag2.traps) if (t1.second == t2.second) { merge_fragments(_frag1, _frag2, t1.first - t2.first); return true; } } } return false; }; auto make_move = [&](int d) { cur_pos = cur_pos + dirs[d]; fragments[cur_frag].frontier.erase(cur_pos); fragments[cur_frag].visited.insert(cur_pos); cout << dir_sym[d] << endl; }; auto explore = [&]() { queue Q; map> back; Q.push(frag_pos(cur_frag, cur_pos)); back[Q.front()] = make_pair(Q.front(), -1); while (!Q.empty()) { auto p = Q.front(); Q.pop(); for (int d = 0; d < 4; ++d) { auto np = frag_pos(p.first, p.second + dirs[d]); auto frag = &fragments[p.first]; if (frag->traps.count(np.second)) { np = frag->traps[np.second]; frag = &fragments[np.first]; } if (frag->frontier.count(np.second)) { vector moves; while (back[p].second >= 0) { moves.push_back(back[p].second); p = back[p].first; } while (!moves.empty()) { make_move(moves.back()); moves.pop_back(); get_response(); } make_move(d); return true; } else if (frag->visited.count(np.second) && !back.count(np)) { back[np] = make_pair(p, d); Q.push(np); } } } return false; }; while (true) { get_response(); if (new_fragments >= 4) merge_fragments(fragments.size() - 3, fragments.size() - 1, pos()); while (find_merge()); if (!explore()) break; } if (fragments.size() == 2) { pos offs; // FIXME prove that the assertions below are correct if (!fragments[0].frontier.empty()) { assert(fragments[0].frontier.size() == 1); assert(fragments[1].frontier.size() == 1); assert(fragments[0].traps.size() == 1); assert(fragments[1].traps.size() == 1); offs = *fragments[0].frontier.begin() - fragments[1].traps.begin()->first; } else { assert(fragments[0].traps.size() == 1); assert(fragments[1].traps.size() == 1); offs = fragments[0].traps.begin()->first - fragments[1].traps.begin()->first; } merge_fragments(0, 1, offs); } assert(fragments.size() == 1); assert(fragments[0].frontier.empty()); cout << "done\n"; fragments[0].show(); }