首页 > 代码库 > HDU-4470-Lights Against Dudely(暴力枚举)

HDU-4470-Lights Against Dudely(暴力枚举)

这道题一开始看上去枚举就可以了,但是最后发现一共有12种情况,开始没数齐。最后怎么交都是WA,最后发现边界没处理,好吧,我也懒得弄了,先放在这。


#include<stdio.h>
#include<string>
#include<sstream>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
int grid[201][201],is_legal[201][201];
int main()
{
    int n,m;
    while(cin>>n>>m && n && m)
    {
        memset(grid,0,sizeof(grid));
        memset(is_legal,0,sizeof(is_legal));
        char temp;int flag = 1;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
            {
                cin>>temp;
                if(temp == '#') {grid[i][j] = 1;is_legal[i][j] = 1;}
                if(temp == '.') {grid[i][j] = 0;is_legal[i][j] = 0;}
            }
        int sum = 0;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
            {
                int flagt = 0;
                if(i != n - 1 && j != m - 1)
                {
                    if(!grid[i][j] && !grid[i][j + 1] && !grid[i + 1][j + 1] && (!is_legal[i][j] || !is_legal[i][j + 1] && !is_legal[i + 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j + 1] = 1;is_legal[i + 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j + 1] && !grid[i + 1][j] && (!is_legal[i][j] || !is_legal[i][j + 1] && !is_legal[i + 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j + 1] = 1;is_legal[i + 1][j] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i + 1][j] && !grid[i + 1][j + 1] && (!is_legal[i][j] || !is_legal[i + 1][j] && !is_legal[i + 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i + 1][j] = 1;is_legal[i + 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(i != n - 1 && j != 0)
                {
                    if(!grid[i][j] && !grid[i + 1][j - 1] && !grid[i + 1][j] && (!is_legal[i][j] || !is_legal[i + 1][j - 1] && !is_legal[i + 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i + 1][j - 1] = 1;is_legal[i + 1][j] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i + 1][j] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i + 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i + 1][j] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i + 1][j - 1] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i + 1][j - 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i + 1][j - 1] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(i != 0 && j != m - 1)
                {
                    if(!grid[i][j] && !grid[i - 1][j] && !grid[i][j + 1] && (!is_legal[i][j] || !is_legal[i - 1][j] && !is_legal[i][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i - 1][j] = 1;is_legal[i][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i - 1][j] && !grid[i - 1][j + 1] && (!is_legal[i][j] || !is_legal[i - 1][j] && !is_legal[i - 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i - 1][j] = 1;is_legal[i - 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j + 1] && !grid[i - 1][j + 1] && (!is_legal[i][j] || !is_legal[i][j + 1] && !is_legal[i - 1][j + 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j + 1] = 1;is_legal[i - 1][j + 1] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(i != 0 && j != 0)
                {
                    if(!grid[i][j] && !grid[i - 1][j] && !grid[i - 1][j  - 1] && (!is_legal[i][j] || !is_legal[i - 1][j] && !is_legal[i - 1][j - 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i - 1][j] = 1;is_legal[i - 1][j - 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i - 1][j  - 1] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i - 1][j - 1]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i - 1][j - 1] = 1;
                        sum++;flagt = 1;
                    }
                    else if(!grid[i][j] && !grid[i][j - 1] && !grid[i - 1][j] && (!is_legal[i][j] || !is_legal[i][j - 1] && !is_legal[i - 1][j]))
                    {
                        is_legal[i][j] = 1;is_legal[i][j - 1] = 1;is_legal[i - 1][j] = 1;
                        sum++;flagt = 1;
                    }
                }
                if(!flagt && !is_legal[i][j]) {flag = 0;break;}  //一开始没判断这里,没及时退出,会出错
            }
            int wandan = 0;
            if(wandan || !flag) printf("-1\n");
            else printf("%d\n",sum);
    }
    return 0;
}




未通过的数据(边界没处理好):

4 4 
.##. 
..#. 
..#. 
..#. 
2 4 
.##. 
#### 


2 4 
.### 
####