#include #include #include #include #include #include using namespace std; unordered_map > graph; unordered_map> visited; int N; char ex_type; unordered_set visited_2; void DFS(int v){ for(auto n : graph[v]){ if(!visited_2.count(n)){ visited_2.insert(n); DFS(n); int i = n/N; int j = n%N; int i2 = v/N; int j2 = v%N; cout< q; q.push(x.first); visited[x.first]={x.first,0}; while(q.size()){ int v = q.front(); q.pop(); for(auto n : graph[v]){ if(!visited.count(n)){ visited[n]={v, visited[v].second + 1}; q.push(n); } } } } void addEdge(int i1, int j1, int i2, int j2, vector &board){ if(i1<0 || i2 <0 || j1 < 0 || j2 < 0 || i1>N-1 || i2>N-1 || j1 >N-1 || j2>N-1) return; if(board[i2][j2] != ex_type) return; int k = i1*N+j1; int z = i2*N+j2; graph[k].insert(z); graph[z].insert(k); } void addKings(vector &board){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(board[i][j]=='K'){ addEdge(i,j,i-1,j, board); addEdge(i,j,i,j-1, board); addEdge(i,j,i+1,j, board); addEdge(i,j,i,j+1, board); addEdge(i,j,i-1,j-1, board); addEdge(i,j,i+1,j+1, board); addEdge(i,j,i-1,j+1, board); addEdge(i,j,i+1,j-1, board); } } } } void fillLine(vector &found){ for( int k = 0; k < found.size(); k++){ if(!graph.count(found[k])) graph[found[k]]=set(); for(int z = k+1; z < found.size(); z++){ graph[found[k]].insert(found[z]); graph[found[z]].insert(found[k]); } } } void construct_graph(vector &board){ if(ex_type == 'R' || ex_type == 'Q'){ vector found; for(int i = 0; i < N; i++){ found.clear(); for(int j = 0; j < N; j++){ if(board[i][j]==ex_type) found.push_back(i*N+j); } fillLine(found); } for(int j = 0; j < N; j++){ found.clear(); for(int i = 0; i < N; i++){ if(board[i][j]==ex_type) found.push_back(i*N+j); } fillLine(found); } } if(ex_type == 'B' || ex_type == 'Q'){ unordered_map > found; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(board[i][j]==ex_type) found[i+j].push_back(i*N+j); } } for(auto elem: found){ fillLine(elem.second); } found.clear(); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(board[i][j]==ex_type) found[i-j].push_back(i*N+j); } } for(auto elem: found){ fillLine(elem.second); } } if(ex_type == 'K'){ addKings(board); } } int main(){ cin>>N; vector board(N); cin >> ex_type; for(int i = 0; i< N; i++) cin>>board[i]; construct_graph(board); BFS(); if(visited.size() != graph.size()){ cout<<"NO"<