为了保证胜利且每个格子只能走一次,所以当遇到地雷或检测到该格子周围存在地雷的时候就需要停止搜索,那么如何知道当前的格子的周围是否存在地雷呢?
可以用一个二维数组 n u m num num来统计每个位置周围的地雷数量,例如,当前位置为 ( 2 , 2 ) (2,2) (2,2)则就需要查看 ( 1 , 1 ) (1,1) (1,1) ( 1 , 2 ) (1,2) (1,2) ( 1 , 3 ) (1,3) (1,3) ( 2 , 1 ) (2,1) (2,1) ( 2 , 3 ) (2,3) (2,3) ( 3 , 1 ) (3,1) (3,1) ( 3 , 2 ) (3,2) (3,2) ( 3 , 3 ) (3,3) (3,3)的位置是否存在地雷,如果存在就把 ( 2 , 2 ) (2,2) (2,2)位置的地雷数量 + 1 +1 +1。由于题目中求最小点击次数,在我们每次点击 0 0 0位置时,其周围的所有 0 0 0都会被点亮,所以我们可以把每个为 0 0 0的位置进行搜索并进行标记表示已经扫描过了一次,并且将点击次数 + 1 +1 +1。最后再进行一次遍历,将所有状态不为 0 0 0的格子进行点击即可求出最小点击次数。
#include
using namespace std;
const int N=310;
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={1,0,-1,1,-1,1,0,-1};
char m[N][N]; //整个的地图
int num[N][N]; //显示的数字
bool vis[N][N]; //遍历的记录
int t,n;
int res=0;
void dfs(int x,int y) //遍历0周围所有的点,标记并且将该点设置为不可点击
{
vis[x][y]=1;
num[x][y]=-1;
for(int i=0;i<8;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx0) //标记已经遍历
{
vis[nx][ny]=1;
num[nx][ny]=-1;
}
if(num[nx][ny]==0) dfs(nx,ny);
}
}
}
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d",&n);
for(int j=0;j>m[j];
memset(num,0,sizeof(num)); //每次循环记得清空数组
for(int j=0;j=0 && x=0 && y
明日预告:网络分析
准备趁着清明节假期啃块硬骨头。