//众神云集、群魔乱舞、以一抵百、砥砺前行//Problem L: Logic Puzzle

缺乏、安全感 2023-02-14 01:48 20阅读 0赞

## 题目描述 ##

While browsing a kiosk at a recent trip, you bought a magazine filled with various kinds of logic  
puzzles. After a while of solving, however, you start to get a bit bored of the puzzles. Still  
wanting to complete all the puzzles in the magazine, you start wondering about ways to solve  
some of them algorithmically.  
The puzzle you are currently trying to solve is called Mosaic, and it is quite similar to the classic  
Minesweeper video game:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xlb196ZWh1YWx1bw_size_16_color_FFFFFF_t_70]  
Figure L.1: Illustration of the first sample  
You are given a two-dimensional grid of cells, initially all white, and you have to color some of  
the cells in black. You are also given a grid of clue numbers, which extends beyond the borders  
of the puzzle grid by one cell in each direction. The number in a cell indicates (exactly) how  
many cells in the 3 × 3 block centered at this cell need to be colored in black. You may not color  
any cells outside of the original grid.  
Input  
The input consists of:  
• one line with two integers h, w (1 ≤ h, w ≤ 100), the height and width of the puzzle;  
• h + 2 lines, each with w + 2 integers c1, . . . , cw+2 (0 ≤ ci ≤ 9), the clue numbers.  
Output  
If the given clue numbers are inconsistent, output impossible. Otherwise, output h lines  
with w characters each, the solution to the puzzle. Use X for black cells and . for white cells. If  
there are multiple solutions, any of them will be accepted.  
Sample Input 1 Sample Output 1  
2 3  
1 1 2 1 1  
1 2 3 2 1  
1 2 3 2 1  
0 1 1 1 0  
X.X  
.X.  
GCPC 2018 – Problem L: Logic Puzzle 23  
Sample Input 2 Sample Output 2  
1 2  
0 0 1 1  
0 1 1 1  
0 1 1 1  
impossible

## 题解 ##

有点可惜，比赛后四分钟才A的，看少了一行  
指导思想：农村包围城市。  
a\[i\]\[j\]的数字决定了an\[i+1\]\[j+1\]是白格还是黑格。若a\[i\]\[j\]>0的话，a\[i+1\]\[j+1\]对应的九宫格内的数字全部减一；在一次内层(列)循环结束后，判断该行的数字是否==0，若不等于0则impossible。

代码如下：

#include<algorithm>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<cmath>
    using namespace std;
    #define ll long long
    #define maxn 0x3f3f3f3f
    int read()
    {
        
        int sign=1,ans=0;
        char ch;
        ch=getchar();
        while(ch<'0'||ch>'9')
        {
        
            if(ch=='-')
                sign=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
        
            ans=(ans<<1)+(ans<<3)+(ch^48);
            ch=getchar();
        }
        return ans*sign;
    }
    int map1[105][105];
    int ans[105][105];
    int main()
    {
        
        memset(ans,0,sizeof(ans));
        int n,m;
        cin>>n>>m;
        for(int i=1; i<=n+2; i++)
            for(int j=1; j<=m+2; j++)
                map1[i][j]=read();
        for(int i=1; i<=n; i++)
        {
        
            for(int j=1; j<=m; j++)
            {
        
                if(map1[i][j]>0)
                {
        
                    ans[i][j]=1;
                    map1[i][j+1]--;
                    map1[i][j]--;
                    map1[i][j+2]--;
                    map1[i+1][j+1]--;
                    map1[i+1][j+2]--;
                    map1[i+1][j]--;
                    map1[i+2][j+1]--;
                    map1[i+2][j+2]--;
                    map1[i+2][j]--;
                }
                else if(map1[i][j]<0)
                {
        
                    cout<<"impossible"<<'\n';
                    return 0;
                }
            }
            for(int k=1; k<=m+2; k++)
            {
        
                if(map1[i][k]!=0)
                {
        
                    cout<<"impossible"<<'\n';
                    return 0;
                }
            }
        }
        for(int i=n; i<=n+2; i++)
        {
        
            for(int j=1; j<=m+2;j++)
            {
        
                if(map1[i][j]!=0)
                {
        
                    cout<<"impossible"<<'\n';
                    return 0;
                }
            }
        }
        for(int i=1; i<=n; i++)
        {
        
            for(int j=1; j<=m; j++)
            {
        
                if(ans[i][j]==1)
                    cout<<"X";
                else
                    cout<<".";
            }
            cout<<'\n';
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xlb196ZWh1YWx1bw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530171319656.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xlb196ZWh1YWx1bw==,size_16,color_FFFFFF,t_70