暴力法+轰炸与排雷 综合法 的 简化版 完成 Minesweeper

解题思路:

给出2种解法，时间复杂度几乎一样，但空间复杂度约为一半的关系。

注意事项:

暴力法：

1.int s[102][102] = {0}为通用写法，若使用c++14，可使用int s[x+2][y+2] = {0}；
2.需要设置一个计数变量cnt，放在while循环外 且 赋初值1 （为了输出 Field #1: 这种语句）；
3.s[i][j] = -100 表示该点为雷区（后面通过判断 值若小于0，则为雷区，输出* ），被邻接的区域++ 后，还是负；
4.需要将 雷区的附近 8个区域的个数++；
5.puts("")表示换行
6.while((cin >> x >> y) && x && y) 接受 不为0的2个输入 （若不满足，则跳出）

轰炸与排雷 综合法：

改进暴力法（仅使用 排雷法），根据雷块 和 安全快 相对数量 来选择判断 （若雷块多，则判断雷块，使用排雷法，即Sweepmine）

参考代码:

暴力法（简单 但空间复杂度较高）

#include <bits/stdc++.h>
using namespace std;
int main(){
	int x, y, cnt = 1;
	char t;
	while((cin >> x >> y) && x && y){
		int s[102][102] = {0};
		for(int i = 1; i <= x; i ++)
			for(int j = 1; j <= y; j ++){
				cin >> t;
				if(t == '*'){
					s[i][j] = -100;
					s[i][j + 1] ++;
					s[i][j - 1] ++;
					s[i + 1][j] ++;
					s[i + 1][j + 1] ++;
					s[i + 1][j - 1] ++;
					s[i - 1][j] ++;
					s[i - 1][j + 1] ++;
					s[i - 1][j - 1] ++;	
				}
			}
		printf("Field #%d:\n", cnt++);	
		for(int i = 1; i <= x; i ++){
			for(int j = 1; j <= y; j ++)
				if(s[i][j] >= 0)
					printf("%d", s[i][j]);	
				else
					printf("*");
			puts("");		
		}
		puts("");					
	}
	return 0;
}

//轰炸与排雷 综合法（复杂 但空间复杂度较低）
#include <stdio.h>
int    X, Y, M, N = 0;
int    num_mine, num_safe; //分别记录雷快的数目，和安全块的数目
int    num = 1;
char    b[100][100];
void Minesweeper( int x, int y ){//轰炸法
    for ( int i = x; i <= x + 2; i++ )
        for ( int j = y; j <= y + 2; j++ )
            if ( i >= 0 && i < X && j >= 0 && j < Y && b[i][j] != '*' )
                b[i][j] += 1;
}
void Sweepmine( int x, int y ){//排雷法
    for ( int i = x; i <= x + 2; i++ )
        for ( int j = y; j <= y + 2; j++ )
            if ( i >= 0 && i < X && j >= 0 && j < Y && b[i][j] == '*' )
                b[x + 1][y + 1] += 1;
}
int main(){
    while (scanf("%d%d", &X, &Y) && !(X == 0 && Y == 0)){
        num_mine = 0; num_safe = 0;
        for ( int i = 0; i < X; i++ )
            for ( int j = 0; j < Y; j++ ){
                scanf(" %c", *(b + i) + j);
                if ( b[i][j] == '.' ){
                    b[i][j] = '0';
                    num_safe++;
                }else
                    num_mine++;
            }
        N++; /*the token of field;*/
        if ( num_mine <= num_safe ){ //判断用哪种方法
            for ( int i = 0; i < X; i++ )
                for ( int j = 0; j < Y; j++ )
                    if ( b[i][j] == '*' )
                        Minesweeper( i - 1, j - 1 );
        }else  {
            for ( int i = 0; i < X; i++ )
                for ( int j = 0; j < Y; j++ )
                    if ( b[i][j] != '*' )
                        Sweepmine( i - 1, j - 1 );
        }
        printf( "Field #%d:\n", N );
        for ( int i = 0; i < X; i++ )
            for ( int j = 0; j < Y; j++ ){
                printf( "%c", b[i][j] );
				if((j + 1) % Y == 0)
                    printf("\n");
            }
        printf("\n");
    }
}