TOJ3184 Mine sweeping dfs

迷南。 2022-05-19 11:14 136阅读 0赞

## **3184: Mine sweeping** ##

**描述**

I think most of you are using system named of xp or vista or win7.And these system is consist of a famous game what is mine sweeping.You must have played it before.If you not,just look the game rules followed.  
  
There are N\*N grids on the map which contains some mines , and if you touch that ,you lose the game.If a position not containing a mine is touched, an integer K (0 < =K <= 8) appears indicating that there are K mines in the eight adjacent positions. If K = 0, the eight adjacent positions will be touched automatically, new numbers will appear and this process is repeated until no new number is 0. Your task is to mark the mines' positions without touching them.  
  
Now, given the distribution of the mines, output the numbers appearing after the player's first touch.

**输入**

The first line of each case is two numbers N (1 <= N <= 100) .Then there will be a map contain N\*N grids.The map is just contain O and X.'X' stands for a mine, 'O' stand for it is safe with nothing. You can assume there is at most one mine in one position. The last line of each case is two numbers X and Y(0<=X<N,0<=Y<N, indicating the position of the player's first touch.

**输出**

If the player touches the mine, just output "it is a beiju!".  
  
If the player doesn't touch the mine, output the numbers appearing after the touch. If a position is touched by the player or by the computer automatically, output the number. If a position is not touched, output a dot '.'.  
  
Output a blank line after each test case.

**样例输入**

5  
OOOOO  
OXXXO  
OOOOO  
OXXXO  
OOOOO  
1 1  
5  
OOOOO  
OXXXO  
OOOOO  
OXXXO  
OOOOO  
0 0

**样例输出**

**it is a beiju!**

**1....  
.....  
.....  
.....  
.....**

扫雷，先判断初始点是否为地雷，如果是的话直接输出“it is a beiju!”，否则从起始点开始搜，每一个‘O’判断8个方向是否有地雷，如果有1个则为1,有2个则为2，以此类推，然后如果有一个数字非0，则结束搜索，输出数字，没有搜到的地方不统计数字。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long	
    bool v[110][110];
    char show[110][110];
    int n;
    int fx[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};
    bool f(int i,int j)
    {
    	if(i>=0&&i<n&&j>=0&&j<n&&v[i][j])
    		return 1;
    	else
    		return 0;
    }
    void dfs(int i,int j)
    {
    	if(i<0||i>=n||j<0||j>=n||show[i][j]||f(i,j))
    		return;
    	for(int k=0;k<8;k++)
    	{
    		int x=i+fx[k][0];
    		int y=j+fx[k][1];		
    		if(f(x,y))
    		show[i][j]++;
    	}
    	show[i][j]+='0';
    	if(show[i][j]=='0')
    	{
    		for(int k=0;k<8;k++)
    		{
    			int x=i+fx[k][0];
    			int y=j+fx[k][1];
    			dfs(x,y);
    		}		
    	}
    }
    int main()
    {
    	int i,j,x,y;
    	while(scanf("%d",&n)!=EOF)
    	{	
    		for(i=0;i<n;i++)
    		{	
    			getchar();
    			for(j=0;j<n;++j)
    			{
    				show[0][0]=getchar();
    				if(show[0][0]=='O')
    					v[i][j] = 0;
    				else
    					v[i][j] = 1;
    			}
    		}
    		scanf("%d%d",&x,&y);
    		if(v[x][y])
    			printf("it is a beiju!\n\n");
    		else
    		{
    			memset(show,0,sizeof(show));
    			dfs(x,y);
    			for(i=0;i<n;++i)
    			{
    				for(j=0;j<n;++j)
    				{
    					if(show[i][j])
    						printf("%c",show[i][j]);
    					else
    						printf(".");
    				}
    				printf("\n");
    			}
    			printf("\n");
    		}
    	}
    }