题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2410

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

001110

......

2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛

一道搜索题，比赛时就是研究这道题，和高恒一起，话说当时方向对了，解题思路很正确，但是编程时候出了点问题。尤其是最后的代码输出，输出一个字符和一个空格。。。其实应该没有空格的。。。o(╯□╰)o啊。。。

言归正传：

这道题题意很简单，扫雷玩过吧？

上面的数字3，代表该点八个方向上有三颗雷。

这道题题意也差不多，只是数字所代表的是 上下左右与该点   五个方向的雷数量。

题目会给出数字，让你确定 雷的分布图，每个数据只输出一个解。

DFS，深度优先搜索。

大体的思路方向是：

从0,0开始往后判断，每个点是否放雷，依据就是周围的数字（上下左右）是否有0的情况，有0就不放雷。

放雷后就要将五个方向的数字减1，然后继续往后判断。

这是主要的判断，但是显然需要大的前提来 剪掉大半棵树。

→首先将第一行枚举，然后每一行根据上一行状态来做：

如果上一行同位置数字为0，则该点不放雷。

如果上一行同位置数字为1，则该点必须放雷，此时判断四周是否有0的情况，没有则放雷，有则回溯。

如果上一行同位置数字不为0或者1，则回溯。

判断到最后一行，需要将最后一行数组判断，是否全为0，是则输出结果，不是则回溯。

就是这样！

#include <iostream>
#include <string.h>
using namespace std;
#define MAX 25
int n,m,num[MAX][MAX],dis[5][2]={0,0,1,0,-1,0,0,1,0,-1};
char Map[MAX][MAX];
bool ispos;
// 判断出界
bool isout(int x,int y)
{
    if( x<0 || y<0 || x>=n || y>=m )    return 1;
    return 0;
}
// 判断五个点是否有小于等于0的位置
bool location(int x,int y)
{
    int i,xx,yy;
    for(i=0;i<5;++i)
    {
        xx=x+dis[i][0];
        yy=y+dis[i][1];
        if( !isout(xx,yy) && num[xx][yy]<=0 )   return false;
    }
    return true;
}
// 如果放雷，五个点数字减1
void change(int x,int y)
{
    int i,xx,yy;
    for(i=0;i<5;++i)
    {
        xx=x+dis[i][0];
        yy=y+dis[i][1];
        if( isout(xx,yy) )  continue;
        --num[xx][yy];
    }
}
// 如果该地原来放雷，但是应该不放，回溯，五个点数字加1
void c_back(int x,int y)
{
    int i,xx,yy;
    for(i=0;i<5;++i)
    {
        xx=x+dis[i][0];
        yy=y+dis[i][1];
        if( isout(xx,yy) )  continue;
        ++num[xx][yy];
    }
}
// 判断最后一行是否符合条件
bool judge_final(void)
{
    int i;
    for(i=0;i<m;++i)
        if( num[n-1][i]!=0 )    return false;
    return true;
}
// 输出结果
void print(void)
{
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
            cout<<Map[i][j];
        cout<<endl;
    }
}
void dfs(int x,int y)
{
    if( ispos ) return;
    if( x==n )
    {
        if( judge_final() )
        {ispos=1;print();}
        return;
    }
    if( y==m )  {dfs(x+1,0);return;}
    if( x==0 )  // 首先第一行要进行枚举，不冲突即可
    {
        if( location(x,y) )
        {
            Map[x][y]=‘*‘;
            change(x,y);
            dfs(x,y+1);
            c_back(x,y);
        }
        Map[x][y]=‘.‘;
        dfs(x,y+1);
    }
    else// 其余行，根据上一行相应位置来判断如果做
    {
        if( num[x-1][y]==0 )    // 上一行为0，此行不能放雷
        {
            Map[x][y]=‘.‘;
            dfs(x,y+1);
        }
        else if( num[x-1][y]==1 )   // 上一行为1，此行必须放雷，判断四周是否有0情况
            if( location(x,y) )
            {
                Map[x][y]=‘*‘;
                change(x,y);
                dfs(x,y+1);
                c_back(x,y);
            }
    }
}

int main()
{
    int i,j,test,t_num;
    char c;
    cin>>test;
    for(t_num=1;t_num<=test;++t_num)
    {
        cin>>n>>m;
        for(i=0;i<n;++i)
            for(j=0;j<m;++j)
            {
                cin>>c;
                num[i][j]=c-‘0‘;
            }
        cout<<"Case "<<t_num<<":"<<endl;
        ispos=0;
        dfs(0,0);
    }
    return 0;
}

[2012山东省第三届ACM大学生程序设计竞赛]——Mine Number