#include #include #include using namespace std; typedef struct fig { bool found; int x, y; fig *prev; } fig; fig* make_new_fig(int x, int y) { fig* new_fig = (fig*)malloc(sizeof(fig*)); new_fig->found = false; new_fig->prev = nullptr; new_fig->x = x; new_fig->y = y; return new_fig; } int main() { int n; cin >> n; queue q; vector toprint; int figcount = 0; vector> board(n, vector(n, nullptr)); char type; cin >> type; bool frst = true; int dequeued = 0; //načítání scanf("\n"); for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { char input; scanf("%c", &input); if (input == type) { figcount++; fig* curr = make_new_fig(x, y); if (frst) { curr->found = true; q.push(curr); toprint.push_back(curr); frst = false; } board[x][y] = curr; //printf("struct XY %i %i\n", board[x][y]->x, board[x][y]->y); } } if(x != n - 1) { scanf("\n"); } } for(int x = 0; x < n; x++) { for(int y = 0; y < n; y++) { if(board[x][y] == nullptr) { //printf("."); } else { //printf("%c %i %i, ", type, board[x][y]->x, board[x][y]->y); } } //printf("\n"); } if(figcount == 1) { printf("YES\n"); return 0; } int fig_moves_R[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int fig_moves_B[][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; int fig_moves_Q[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; int fig_moves_K[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; int fig_moves_N[][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; if (type == 'K' || type == 'N') { while (q.front() != nullptr) { fig *currfig = q.front(); dequeued++; //printf("curr dequeued %i\n", dequeued); int currx; int curry; for (int j = 0; j < 8; j++) { if (type == 'K') { currx = currfig->x + fig_moves_K[j][0]; curry = currfig->y + fig_moves_K[j][1]; } else { currx = currfig->x + fig_moves_N[j][0]; curry = currfig->y + fig_moves_N[j][1]; } if (currx < n && currx >= 0 && curry < n && curry >= 0 && board[currx][curry] != nullptr && !board[currx][curry]->found) { //printf("found one\n"); board[currx][curry]->found = true; board[currx][curry]->prev = currfig; q.push(board[currx][curry]); toprint.push_back(board[currx][curry]); } } q.pop(); } } else if (type == 'Q') { while (q.front() != nullptr) { fig *currfig = q.front(); dequeued++; //printf("curr dequeued %i\n", dequeued); for (int i = 1; i < n; i++) { for (int j = 0; j < 8; j++) { int currx = currfig->x + fig_moves_Q[j][0] * i; int curry = currfig->y + fig_moves_Q[j][1] * i; if (currx < n && currx >= 0 && curry < n && curry >= 0 && board[currx][curry] != nullptr && !board[currx][curry]->found) { board[currx][curry]->found = true; board[currx][curry]->prev = currfig; q.push(board[currx][curry]); toprint.push_back(board[currx][curry]); } } } q.pop(); } } else //bishop or rook { while (q.front() != nullptr) { fig *currfig = q.front(); dequeued++; //printf("curr dequeued %i\n", dequeued); int currx; int curry; for (int i = 1; i < n; i++) { for (int j = 0; j < 4; j++) { if (type == 'B') { currx = currfig->x + fig_moves_B[j][0] * i; curry = currfig->y + fig_moves_B[j][1] * i; } else { currx = currfig->x + fig_moves_R[j][0] * i; curry = currfig->y + fig_moves_R[j][1] * i; } if (currx < n && currx >= 0 && curry < n && curry >= 0 && board[currx][curry] != nullptr && !board[currx][curry]->found) { board[currx][curry]->found = true; board[currx][curry]->prev = currfig; q.push(board[currx][curry]); toprint.push_back(board[currx][curry]); } } } q.pop(); } } if (dequeued != figcount) { printf("NO\n", figcount); } else { printf("YES\n"); for (int i = toprint.size() - 1; i > 0; i--) { printf("%i %i %i %i\n", toprint[i]->x+1, toprint[i]->y+1, toprint[i]->prev->x+1, toprint[i]->prev->y+1); } } return 0; }