#include #include #include #include #include using namespace std; #define ll long long #define FOR(i, L, R) for (int i = L; i < R; i++) #define pb push_back #define pii pair #define vi vector int getPos(char k){ if (k=='R'){ return 0; } else if (k=='Q'){ return 1; } else if (k=='B'){ return 2; } else if (k=='N'){ return 3; } else if (k=='K'){ return 4; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ///----------------------------- int test_cases = 1; while (test_cases--) { int n; cin >> n; char exc_type; cin >> exc_type; char city[n][n]; int exc_n = 0; FOR(i, 0, n){ string line; cin >> line; FOR(j,0,n){ city[i][j]=line[j]; if(line[j]!='.') ++exc_n; //cout<> ngbrs[100][100]; int curr = -1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { curr++; if(city[i][j]=='.'){ continue; } else if(city[i][j]=='R'){ // na stejnem radku for(int c = 0; c < n; c++){ if(city[i][c]!='.'){ ngbrs[i][j].push_back(make_pair(i,c)); } } // ve stejnem sloupci for(int r = 0; r < n; r++){ if(city[r][j]!='.'){ ngbrs[i][j].push_back(make_pair(r,j)); } } } else if(city[i][j]=='Q'){ // na stejnem radku for(int c = 0; c < n; c++){ if(city[i][c]!='.'){ ngbrs[i][j].push_back(make_pair(i,c)); } } // ve stejnem sloupci for(int r = 0; r < n; r++){ if(city[r][j]!='.'){ ngbrs[i][j].push_back(make_pair(r,j)); } } // nakrivo z pos do 0 0 { pair nexttile = make_pair(i-1,j-1); while(nexttile.first>=0 && nexttile.second>=0){ if(city[nexttile.first][nexttile.second]!='.'){ ngbrs[i][j].push_back(nexttile); } nexttile= make_pair(nexttile.first-1,nexttile.second-1); } } // nakrivo z pos do n n { pair nexttile = make_pair(i + 1, j + 1); while (nexttile.first < n && nexttile.second < n) { if (city[nexttile.first][nexttile.second] != '.') { ngbrs[i][j].push_back(nexttile); } nexttile = make_pair(nexttile.first + 1, nexttile.second + 1); } } // nakrivo z pos do 0 n { pair nexttile = make_pair(i-1,j+1); while(nexttile.first>=0 && nexttile.second nexttile = make_pair(i + 1, j - 1); while (nexttile.first < n && nexttile.second >= 0) { if (city[nexttile.first][nexttile.second] != '.') { ngbrs[i][j].push_back(nexttile); } nexttile = make_pair(nexttile.first + 1, nexttile.second - 1); } } }else if(city[i][j]=='B'){ // nakrivo z pos do 0 0 { pair nexttile = make_pair(i-1,j-1); while(nexttile.first>=0 && nexttile.second>=0){ if(city[nexttile.first][nexttile.second]!='.'){ ngbrs[i][j].push_back(nexttile); } nexttile= make_pair(nexttile.first-1,nexttile.second-1); } } // nakrivo z pos do n n { pair nexttile = make_pair(i + 1, j + 1); while (nexttile.first < n && nexttile.second < n) { if (city[nexttile.first][nexttile.second] != '.') { ngbrs[i][j].push_back(nexttile); } nexttile = make_pair(nexttile.first + 1, nexttile.second + 1); } } // nakrivo z pos do 0 n { pair nexttile = make_pair(i-1,j+1); while(nexttile.first>=0 && nexttile.second nexttile = make_pair(i + 1, j - 1); while (nexttile.first < n && nexttile.second >= 0) { if (city[nexttile.first][nexttile.second] != '.') { ngbrs[i][j].push_back(nexttile); } nexttile = make_pair(nexttile.first + 1, nexttile.second - 1); } } }else if(city[i][j]=='N'){ pair knmoves[8] = {make_pair(i-2,j-1), make_pair(i-2,j+1), make_pair(i-1,j+2), make_pair(i+1,j+2), make_pair(i+2,j+1), make_pair(i+2,j-1), make_pair(i+1,j-2), make_pair(i-1,j-2)}; for (auto move : knmoves){ if(move.first>=0 && move.first=0 && move.second kmoves[8] = {make_pair(i-1,j-1), make_pair(i-1,j), make_pair(i-1,j+1), make_pair(i,j-1), make_pair(i,j+1), make_pair(i+1,j-1), make_pair(i+1,j), make_pair(i+1,j+2)}; for (auto move : kmoves){ if(move.first>=0 && move.first=0 && move.second pocatek; for(int i = 0; i < n; ++i){ for (int j = 0; j < n; ++j) { if(city[i][j]!='.'){ pocatek = make_pair(i,j); } } } queue> f; f.push(pocatek); vector> kostra[100][100]; bool visited[100][100] = {}; int vcount = 1; visited[pocatek.first][pocatek.second]=true; while(!f.empty()){ pair curr = f.front(); f.pop(); for(auto soused: ngbrs[curr.first][curr.second]){ if(visited[soused.first][soused.second]){ continue; } visited[soused.first][soused.second]=true; kostra[curr.first][curr.second].push_back(soused); kostra[soused.first][soused.second].push_back(curr); f.push(soused); ++vcount; } } /*5 N ...N. .N... ..N.. N.... .....*/ /* 1 N N */ if(vcount!=exc_n){ cout<<"NO"<1){ for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(kostra[i][j].size()==1){ cout << i + 1 << " " << j + 1 << " " << kostra[i][j][0].first+1 << " " << kostra[i][j][0].second+1 << endl; auto position = std::find(kostra[kostra[i][j][0].first][kostra[i][j][0].second].begin(), kostra[kostra[i][j][0].first][kostra[i][j][0].second].end(), make_pair(i, j)); //if (position != myVector.end()) // == myVector.end() means the element was not found kostra[kostra[i][j][0].first][kostra[i][j][0].second].erase(position); kostra[i][j].pop_back(); vcount--; } } } } } return 0; }