#include #include using namespace std; typedef pair ii; const int MAXN = 200; int n, cnt, solcnt; char t; char mat[MAXN][MAXN]; bool vis[MAXN][MAXN]; int sol[MAXN*MAXN][4]; const int NDX[] = {-2, -2, -1, -1, 1, 1, 2, 2}; const int NDY[] = {-1, 1, -2, 2, -2, 2, -1, 1}; const int KDX[] = {-1, -1, -1, 0, 0, 1, 1, 1}; const int KDY[] = {-1, 0, 1, -1, 1, -1, 0, 1}; bool valid(int x, int y){ return 0<=x && x neighbours(int x, int y){ vector res; switch(t){ case 'R': for(int i=x+1;i=0;i--) if(mat[i][y] != '.'){ res.push_back(ii(i, y));break;} for(int i=y+1;i=0;i--) if(mat[x][i] != '.'){ res.push_back(ii(x, i));break;} break; case 'Q': for(int i=x+1;i=0;i--) if(mat[i][y] != '.'){ res.push_back(ii(i, y));break;} for(int i=y+1;i=0;i--) if(mat[x][i] != '.'){ res.push_back(ii(x, i));break;} for(int i=1;x+i=0;i++) if(mat[x+i][y-i] != '.'){ res.push_back(ii(x+i,y-i)); break;} for(int i=1;x-i>=0 && y-i>=0;i++) if(mat[x-i][y-i] != '.'){ res.push_back(ii(x-i,y-i)); break;} for(int i=1;x-i>=0 && y+i=0;i++) if(mat[x+i][y-i] != '.'){ res.push_back(ii(x+i,y-i)); break;} for(int i=1;x-i>=0 && y-i>=0;i++) if(mat[x-i][y-i] != '.'){ res.push_back(ii(x-i,y-i)); break;} for(int i=1;x-i>=0 && y+i