第十三届JAVA研究生组决赛—— 6.点亮
import java.io.*;
import java.util.*;
public class Main{
public static Scanner sc = new Scanner(System.in);
public static final int N = 6;
public static char[][] map = new char[N][N];
public static int n;
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static boolean check() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(map[i][j] == '.') return false;
if((map[i][j] - 48) >= 0 && (map[i][j] - 48) <= 4) {
int count = 0;
for(int k = 0; k < 4; k++) {
int a = i + dx[k]; int b = j + dy[k];
if(a >= 1 && a <= n && b >= 1 && b <= n && map[a][b] == 'O') count++;
}
if(count != (map[i][j] - 48)) return false;
}
}
}
return true;
}
public static void shine(int x, int y) {
for(int j = y-1; j >= 1; j--) {
if(map[x][j] == '.' || map[x][j] == 'S') map[x][j] = 'S';
else break;
}
for(int j = y+1; j <= n; j++) {
if(map[x][j] == '.' || map[x][j] == 'S') map[x][j] = 'S';
else break;
}
for(int i = x+1; i <= n; i++) {
if(map[i][y] == '.' || map[i][y] == 'S') map[i][y] = 'S';
else break;
}
for(int i = x-1; i >= 1; i--) {
if(map[i][y] == '.' || map[i][y] == 'S') map[i][y] = 'S';
else break;
}
}
public static void dfs(int x, int y) {
if(y == n+1) {
y = 1; x++;
}
if(x == n+1) {
if(check()) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(map[i][j] != 'S') System.out.print(map[i][j]);
else System.out.print('.');
}
System.out.println();
}
System.exit(0);
}else {
return;
}
}
if(map[x][y] == '.') {
char temp[][] = new char[N][N];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) temp[i][j] = map[i][j];
map[x][y] = 'O';
shine(x, y);
dfs(x, y+1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) map[i][j] = temp[i][j];
dfs(x, y+1);
}else {
dfs(x, y+1);
}
}
public static void main(String[] args){
n = sc.nextInt();
for(int i = 1; i <= n; i++) {
String line = sc.next();
for(int j = 1; j <= n; j++) map[i][j] = line.charAt(j-1);
}
dfs(1, 1);
}
}