foj 1056 扫雷游戏【递归】

今天药忘吃喽~ 2022-08-10 03:40 255阅读 0赞

Problem 1056 扫雷游戏  
**Accept: 1978    Submit: 5012  
Time Limit: 1000 mSec    Memory Limit : 32768 KB**

**Problem Description**  
扫雷是Windows自带的游戏。游戏的目标是尽快找到雷区中的所有地雷，而不许踩到地雷。如果方块上的是地雷，将输掉游戏。如果方块上出现数字，则表示在其周围的八个方块中共有多少颗地雷。

你的任务是在已知地雷出现位置的情况下，得到各个方块中的数据。

\*...  
....      “\*”表示有地雷  
.\*..      “.”表示无地雷  
....经过处理应得到  
\*100  
2210  
1\*10  
1110

![Center][]

思路分析：记录埋雷的格子，然后以埋雷格子的外围八个格子分别为中心格子，再遍历外围八个格子，看看有多少个雷；

**Input**  
输入有多组数据，每组数据的第一行有两个数字，m,n(0<m,n<100)表示游戏中雷区的范围为m×n。接下来m行每行有n个字符。“\*” 表示有地雷，“.”表示无地雷。最后一组数据m=0,n=0表示输入结束，不需要处理。  
 Output  
对于每组输入数据，输出结果，各方块数字间不留空格。每组结果之后有一个空行。  
**Sample Input**  
2 3  
\*\*\*  
...  
4 4  
\*...  
....  
.\*..  
....  
0 0

**Sample Output**  
\*\*\*  
232

\*100  
2210  
1\*10  
1110

已Accept代码【c++提交】

#include <cstdio>
    #include <cstring>
    #include <stack>
    using namespace std;
    
    char c;
    int n, m;	//雷区的规格 n * m ； 
    int map[101][101];
    
    //当前格子的外围八个格子 
    int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
    int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
    
    struct ak_chen {
    	int x, y;
    }cd[10000];
    
    //遍历当前格子的外围把各个子 
    int Search_eight(int x, int y) {
    	int num = 0;
    	for(int i = 0; i < 8; i++) {
    		if(x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m)//不越界 
    			if(map[x + dx[i]][y + dy[i]] == -1)			//‘-1’为地雷 
    				num++;
    	}
    	return num;
    }
    
    void Find_chen(ak_chen la) {
    	int x = la.x;
    	int y = la.y;
    	for(int i = 0; i < 8; i++) {
    		//遍历当前埋雷的格子的外围八个格子 
    		if(x + dx[i]  >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m)//不越界 
    			if(map[x + dx[i]][y + dy[i]] != -1)//不埋雷 
    				//以这个格子为中心格子，在便利改个字的外围八个格子 
    				map[x + dx[i]][y + dy[i]] = Search_eight(x + dx[i], y + dy[i]);
    	}
    }
    
    int main (){
    	while(scanf("%d%d", &n, &m), n|m) {
    		int q = 0;
    		stack <ak_chen> s;					//用来记录埋雷的格子 
    		memset(map, 0, sizeof(map));
    		for(int i = 0; i < n; i++) {
    			getchar();						//吸收多余换行符 
    			for(int j = 0; j < m; j++) {
    				c = getchar();				//吸收多余换行符 
    				if(c == '*') {
    					map[i][j] = -1;
    					cd[q].x = i;
    					cd[q].y = j;
    					s.push(cd[q]);
    					q++;
    				}
    			}
    		}
    		ak_chen la;
    		while(!s.empty()) {		//对每个埋雷的格子进行遍历 
    			la = s.top();
    			Find_chen(la);
    			s.pop();
    		}
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < m; j++) {
    				if(map[i][j] == -1)
    					printf("*");
    				else
    					printf("%d", map[i][j]);
    			}
    				
    			printf("\n");
    		}
    		printf("\n");		//注意每个例子结束后都有一个空行 
    	}
    	return 0;
    }

[Center]: /images/20220731/e80ef5ceec05483e87509b8e7e15e281.png