import java.io.*; import java.util.*; /** * Recursive backtracking solution. * Make sure that the constraints are not exceeded with each placement and that constraints * are satisfied perfectly if future placements cannot change intersection counts. * Only do the cycle checking if \/ is placed. * * @author Finn Lidbetter */ public class diag_finn { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] gridCounts = new int[n+1][n+1]; for (int i=0; i0 && solution[row][col]=='/' && solution[row][col-1]=='\\') { if (hasCycle(adj, row+1, col)) { return false; } } int[] dr = new int[]{0,0,1,1}; int[] dc = new int[]{0,1,0,1}; for (int i=0; i<4; i++) { int r = row + dr[i]; int c = col + dc[i]; if (gridCounts[r][c]!=-1 && currentCounts[r][c]>gridCounts[r][c]) { return false; } } return true; } static boolean hasCycle(boolean[][][][] adj, int srcRow, int srcColumn) { int n = adj.length - 1; int[][] vis = new int[n+1][n+1]; return cycleDfs(adj, vis, srcRow, srcColumn); } static boolean cycleDfs(boolean[][][][] adj, int[][] vis, int row, int col) { // vis[r][c] = 0 if not visited at all. // vis[r][c] = 1 if currently processing. // vis[r][c] = 2 if finished processing. // Cycle is found if we encounter more than a single 1. vis[row][col] = 1; int[] dr = new int[]{-1,-1,1,1}; int[] dc = new int[]{1,-1,-1,1}; boolean cycleDetected = false; int adjacent1s = 0; for (int i=0; i<4; i++) { int nr = row + dr[i]; int nc = col + dc[i]; if (nr<0 || nr>=vis.length || nc<0 || nc>=vis.length) { continue; } if (adj[row][col][nr][nc]) { if (vis[nr][nc]==1) { adjacent1s++; } else if (vis[nr][nc]==0) { cycleDetected = cycleDetected || cycleDfs(adj, vis, nr, nc); } } } vis[row][col] = 2; if (adjacent1s>1) { cycleDetected = true; } return cycleDetected; } }