扫雷
题意
扫雷游戏，有一个方格，其中若无地雷，则有一数字标识周围雷的数量（8个格子中雷的数量），如果此数字是0， 则点击时会自动递归点击周围8个方格。已知所有雷的位置，问最少点几次可以完成游戏;
思路分析
- 先计算出每个方格的数字，如果当前点是雷，则标注为-1, for循环遍历及可计算
- 之后先点击数字是0的格子，利用dfs扩展，点过的点标注为-1。这里注意每次dfs之前要判断一下，当前点是不是数字为0
- 之后点击剩余的格子， 及for循环遍历计算剩余的不是-1的点
更多题解和算法题分析GitHub
欢迎star 
AC代码
Cpp 
#include <iostream>
using namespace std;
const int N = 310;
char str[N][N];
int g[N][N];
int path[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
int n;
// 如果当前点是0 则可以扩展点击
void dfs(int i, int j){
int c = g[i][j];
g[i][j] = -1;
if(c != 0) return;
for(int k = 0; k < 8; k ++){
int nx = i + path[k][0];
int ny = j + path[k][1];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] != -1){
dfs(nx, ny);
}
}
}
int main(){
int T;
scanf("%d", &T);
for(int I = 1; I <= T; I ++){
scanf("%d", &n);
for(int i = 0; i < n; i ++){
scanf("%s", str[i]);
}
// 先统计每个点的周围的雷的个数
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(str[i][j] == '*'){
g[i][j] = -1;
} else {
g[i][j] = 0;
for(int k = 0; k < 8; k ++){
int nx = i + path[k][0];
int ny = j + path[k][1];
if(nx >= 0 && nx < n && ny >= 0 && ny <= n && str[nx][ny] == '*'){
g[i][j] ++;
}
}
}
}
}
// 先点0点
// 如果当前点是0 则让其扩展
int res = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(g[i][j] == 0){
res ++;
dfs(i, j);
}
}
}
// 点其他点
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(g[i][j] != -1){
res ++;
}
}
}
printf("Case #%d: %d\n", I, res);
}
}
Python 
T = int(input())
for case in range(1, T + 1):
n = int(input())
strr = [[0 for i in range(n + 1)] for _ in range(n + 1)]
g = [[0 for i in range(n + 1)] for _ in range(n + 1)]
path = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]
# 把输入节点的周围八个点都点一遍
def dfs(i, j):
c = g[i][j]
# 讲此点标记
g[i][j] = -1
if c != 0:
return
for item in path:
nx = i + item[0]
ny = j + item[1]
if nx >= 0 and nx < n and ny >= 0 and ny < n and g[nx][ny] != -1:
dfs(nx, ny)
# 输入
for i in range(n):
t = list(map(str, input().strip().split()))
for j in range(n):
strr[i][j] = t[0][j]
# 计算每个点的周围的雷的个数
for i in range(n):
for j in range(n):
if strr[i][j] == '*':
g[i][j] = -1
else:
cnt = 0
for item in path:
nx = i + item[0]
ny = j + item[1]
if nx >= 0 and nx < n and ny >= 0 and ny < n and strr[nx][ny] == '*':
cnt += 1
g[i][j] = cnt
res = 0
# 先点0 的点
for i in range(n):
for j in range(n):
if g[i][j] == 0:
dfs(i, j)
res += 1
# 统计现在还有多少剩余点
for i in range(n):
for j in range(n):
if g[i][j] != -1:
res += 1
print('Case #{}: {}'.format(case, res))
Java
import java.io.*;
import java.util.*;
class Main{
public static final int N = 310;
public static int n;
public static char[][] str = new char[N][N];
public static int[][] g = new int[N][N];
public static int[][] path = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
public static void dfs(int i, int j){
int c = g[i][j];
g[i][j] = -1;
if(c != 0){
return;
}
for(int k = 0; k < 8; k ++){
int nx = i + path[k][0];
int ny = j + path[k][1];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] != -1){
dfs(nx, ny);
}
}
}
public static void main(String[] args) throws IOException{
int T = 0;
// Scanner in = new Scanner(new BufferedInputStream(System.in));
// T = in.nextInt();
AReader in = new AReader(System.in);
T = in.nextInt();
for(int I = 1; I <= T; I ++){
n = in.nextInt();
for(int i = 0; i < n; i ++){
String s = in.nextLine();
for(int j = 0; j < n; j ++){
// str[i][j] = in.nextChar();
str[i][j] = s.charAt(j);
}
}
// 先将每个点标记周围又多少个雷
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(str[i][j] == '*'){
g[i][j] = -1;
} else {
int cnt = 0;
for(int k = 0; k < 8; k ++){
int nx = i + path[k][0];
int ny = j + path[k][1];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && str[nx][ny] == '*'){
cnt ++;
}
}
g[i][j] = cnt;
}
}
}
int res = 0;
//
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(g[i][j] == 0){
dfs(i, j);
res ++;
}
}
}
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(g[i][j] != -1){
res ++;
}
}
}
System.out.println("Case #" + I + ": " + res);
}
}
}
// 输入输出模板来自 https://www.rainng.com/java-acm-fast-io/
class AReader implements Closeable {
private BufferedReader reader;
private StringTokenizer tokenizer;
public AReader(InputStream inputStream) {
reader = new BufferedReader(new InputStreamReader(inputStream));
tokenizer = new StringTokenizer("");
}
private String innerNextLine() {
try {
return reader.readLine();
} catch (IOException ex) {
return null;
}
}
public boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String nextLine = innerNextLine();
if (nextLine == null) {
return false;
}
tokenizer = new StringTokenizer(nextLine);
}
return true;
}
public String nextLine() {
tokenizer = new StringTokenizer("");
return innerNextLine();
}
public String next() {
hasNext();
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
@Override
public void close() throws IOException {
reader.close();
}
}
class AWriter implements Closeable {
private BufferedWriter writer;
public AWriter(OutputStream outputStream) {
writer = new BufferedWriter(new OutputStreamWriter(outputStream));
}
public void print(Object object) throws IOException {
writer.write(object.toString());
}
public void println(Object object) throws IOException {
writer.write(object.toString());
writer.write("\n");
}
@Override
public void close() throws IOException {
writer.close();
}
}
