package icm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.AbstractMap; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Excavation { public static List path = new ArrayList(); static boolean finished; public static void excavate(String piece, List>> grid, Map, Class> piecesLocation, int size, List> from, List> to) { if(piecesLocation.size() == 1) { System.out.println("YES"); for(int i=0; i, Class> en : piecesLocation.entrySet()) { List> validMoves = null; if(en.getValue().getClass().isInstance(Reepadlo.class)) { validMoves = Reepadlo.validMoves(size, en.getKey(), piecesLocation); } if(en.getValue().getClass().isInstance(Qrtech.class)) { validMoves = Qrtech.validMoves(size, en.getKey(), piecesLocation); } if(en.getValue().getClass().isInstance(Bugger.class)) { validMoves = Bugger.validMoves(size, en.getKey(), piecesLocation); } if(en.getValue().getClass().isInstance(Namakatschenko.class)) { validMoves = Namakatschenko.validMoves(size, en.getKey(), piecesLocation); } if(en.getValue().getClass().isInstance(Kopatsch.class)) { validMoves = Kopatsch.validMoves(size, en.getKey(), piecesLocation); } for(Map.Entry validMove : validMoves) { Map, Class> piecesLocationNew = new HashMap<>(piecesLocation); piecesLocationNew.put(validMove, en.getValue()); piecesLocationNew.remove(en.getKey()); List> newFrom = new ArrayList<>(from); List> newTo = new ArrayList<>(to); newFrom.add(en.getKey()); newTo.add(validMove); excavate(piece, grid, piecesLocationNew, size, newFrom, newTo); } } } public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { String[] line1 = br.readLine().split(" "); int size = Integer.parseInt(line1[0]); // String piece = line1[1]; List>> grid = new ArrayList<>(); Map, Class> piecesLocation = new HashMap<>(); for (int i = 0; i < size; i++) { String gridX = br.readLine(); List> row = new ArrayList<>(); gridX.chars().map(c -> (char) c).forEach(ea -> { row.add(getEx((char) ea)); }); grid.add(row); } for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid.get(i).size(); j++) { if (grid.get(i).get(j) != null) { piecesLocation.put(new AbstractMap.SimpleImmutableEntry<>(i, j), grid.get(i).get(j)); } } } excavate("", grid, piecesLocation, size, new ArrayList<>(), new ArrayList<>()); if(path.size() == 0) { System.out.println("NO"); } } catch (IOException e1) { e1.printStackTrace(); } } public static Class getEx(char ex) { switch (ex) { case 'R': return Reepadlo.class; case 'Q': return Qrtech.class; case 'B': return Bugger.class; case 'N': return Namakatschenko.class; case 'K': return Kopatsch.class; } return null; } static class Reepadlo{ public static List> validMoves(int size, Map.Entry position, Map, Class> piecesLocation) { List> moves = new ArrayList<>(); for (int i = 1; i <= (size - position.getKey()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() + i, position.getValue()); if (piecesLocation.containsKey(key)) { moves.add(key); } } for (int i = 1; i <= (position.getKey()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() - i, position.getValue()); if (piecesLocation.containsKey(key)) { moves.add(key); } } for (int i = 1; i <= (size - position.getValue()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey(), position.getValue() + i); if (piecesLocation.containsKey(key)) { moves.add(key); } } for (int i = 1; i <= (position.getValue()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() + i, position.getValue() - i); if (piecesLocation.containsKey(key)) { moves.add(key); } } return moves; } } static class Qrtech { public static List> validMoves(int size, Map.Entry position, Map, Class> piecesLocation) { List> moves = new ArrayList<>(); moves.addAll(Reepadlo.validMoves(size, position, piecesLocation)); moves.addAll(Bugger.validMoves(size, position, piecesLocation)); return moves; } } static class Bugger { public static List> validMoves(int size, Map.Entry position, Map, Class> piecesLocation) { List> moves = new ArrayList<>(); for (int i = 1; i <= (size - position.getKey() < size - position.getValue() ? size - position.getKey() : size - position.getValue()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() + i, position.getValue() + i); if (piecesLocation.containsKey(key)) { moves.add(key); } } for (int i = 1; i <= (position.getKey() < position.getValue() ? position.getKey() : position.getValue()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() - i, position.getValue() - i); if (piecesLocation.containsKey(key)) { moves.add(key); } } for (int i = 1; i <= (position.getKey() < size - position.getValue() ? position.getKey() : size - position.getValue()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() - i, position.getValue() + i); if (piecesLocation.containsKey(key)) { moves.add(key); } } for (int i = 1; i <= (size - position.getKey() < position.getValue() ? size - position.getKey() : position.getValue()); i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() + i, position.getValue() - i); if (piecesLocation.containsKey(key)) { moves.add(key); } } return moves; } } static class Namakatschenko { public static List> validMoves(int size, Map.Entry position, Map, Class> piecesLocation) { List> moves = new ArrayList<>(); Integer[] x = { 2, 1, -2, -1, 2, 1, -2, -1 }; Integer[] y = { 1, 2, 1, 2, -1, -2, -1, -2 }; for (int i = 0; i < 8; i++) { Map.Entry key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() + x[i], position.getValue() + y[i]); if (!(key.getValue() > size || key.getValue() < 0 || key.getKey() > size || key.getKey() < 0)) { if (piecesLocation.containsKey(key)) { moves.add(key); } } } return moves; } } static class Kopatsch { public static List> validMoves(int size, Map.Entry position, Map, Class> piecesLocation) { List> moves = new ArrayList<>(); Byte[] xV = {1,1,1,0,0,-1,-1,-1}; Byte[] yV = {1,0,-1,1,-1,1,0,-1}; for(byte i=0;i key = new AbstractMap.SimpleImmutableEntry<>(position.getKey() + xV[i], position.getValue() + yV[i]); if (!(key.getValue() > size || key.getValue() < 0 || key.getKey() > size || key.getKey() < 0)) { if (piecesLocation.containsKey(key)) { moves.add(key); } } } return moves; } } }