首页 > 搜索 > BFS搜索 > HDU 3316-Mine sweeping-BFS-[解题报告]HOJ
2014
03-16

HDU 3316-Mine sweeping-BFS-[解题报告]HOJ

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.

输出:

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.

样例输入:

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

样例输出:

it is a beiju!

1....
.....
.....
.....
.....

#include<iostream>
#include<queue>
using namespace std;
int dir[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
char map[105][105];
char mark  [105][105];
bool visited [105][105];
struct pos
{
   int x,y,num;
};
int n;
void  bfs(int px,int py)
{
	int tx,ty;
	queue<pos> q;
	pos N,P;
	N.x=px;
	N.y=py;
	N.num=0;
	visited[N.x][N.y]=false;
	q.push(N);
	while(!q.empty())
	{
	   N=q.front();
	   q.pop();
	   for(int i=0;i<8;i++)
	   {
		   
		  tx=N.x+dir[i][0];
		  ty=N.y+dir[i][1];
		  if(tx>=0&&tx<n&&ty>=0&&ty<n)
		  {
          if(map[tx][ty]=='X')
			  N.num++;
		  }
	   }
	    if(N.num==0)
		{
			visited[N.x][N.y]=true;   
			mark[N.x][N.y]='0';
		   for(int i=0;i<8;i++)
		   {	
			
			    tx=N.x+dir[i][0];	
			   ty=N.y+dir[i][1];
			   if(visited[tx][ty]==false&&tx>=0&&tx<n&&ty>=0&&ty<n)
			   {  
				   P.x=tx;
				      P.y=ty;
			     	 P.num=0;
                     q.push(P); 
					 visited[tx][ty]=true;
			   }
		   }
		}
		if(N.num!=0)
		{
			mark[N.x][N.y]=N.num+'0';
		      visited[N.x][N.y]=true;
		}
	}
}
int  main()
{
	int px,py;
	while(cin>>n)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				cin>>map[i][j];
		  cin>>px>>py;
		   for(int i=0;i<n;i++)
			   for(int j=0;j<n;j++)
			   {
				   mark[i][j]='.';
			      visited[i][j]=false;
			   }
			   if(map[px][py]=='X')
				   cout<<"it is a beiju!"<<endl;
			   else
			   {
				   bfs(px,py);
		            for(int i=0;i<n;i++)
		             {
			         for(int j=0;j<n;j++)
	  			        cout<<mark[i][j];
	                    cout<<endl;   
		                }
			        }  
			   cout<<endl;
	}
	return 0;
}
2791261 2010-08-10 15:03:53 Accepted 3316 62MS 300K 1712 B C++ adam

开始TML,在周围雷数位0的时候,往8个方向扫,并且记录VISITED访问过,

错误的认为若标记为VISITED会少些结果,但是,当雷数为0的时候

   if(visited[tx][ty]==false&&tx>=0&&tx<n&&ty>=0&&ty<n)

  {  

  P.x=tx;

     P.y=ty;

    P.num=0;

                     q.push(P); 

visited[tx][ty]=true;

  }

已经加周围点加入到了队列中,所以一定可以标记为记录过。

 

参考:http://blog.csdn.net/hdxiaoyu2/article/details/5801576


,
  1. 3,求得所有的为的总和sum—->所有数的总和
    printf( "Not Possible" );—->printf("impossible");
    对吗?