FZU 1056 扫雷游戏【搜索】

Accept: 2584 Submit: 6790
Time Limit: 1000 mSec Memory Limit :
32768 KB

Problem Description

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

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

*...
.... “*”表示有地雷
.*.. “.”表示无地雷
....

经过处理应得到

*100
2210
1*10
1110

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

Source

FZUPC Warmup 2005

【分析】：本来想BFS，发现忘记队列的一些用法了。最后用的爆搜，几乎没什么剪枝。

【代码】：

#include <iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<streambuf>

#include<cmath>

#include<string>

#include<queue>

using namespace std;

#define ll long long

#define oo 10000000

int n,m,cnt;

char a[][];

bool check(int x,int y)

{

    if(x>=&&x<=n&&y>=&&y<=m&&a[x][y]=='*')

        return true;

    return false;

}

int main()

{

    while(~scanf("%d%d",&n,&m),n&&m)

    {

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                cin>>a[i][j];

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=m;j++)

            {

                if(a[i][j]=='*')

                    cout<<"*";

                else if(a[i][j]=='.')

                {

                    cnt=;

                    for (int k=i-;k<=i+;k++)//八个方向搜索

                    {

                        for (int p=j-;p<=j+;p++)

                        {

                            if (check(k,p)) //合法（不越界+搜到地雷）

                            {

                                cnt++; //每次在八方向搜到一个地雷 计数器+1

                            }

                        }

                    }

                    printf("%d",cnt);

                }

            }

            printf("\n");//注意格式

        }

        printf("\n");

    }

}

暴搜

游戏