YTUOJ-Beautiful Meadow

Description

 Tom‘s Meadow Tom has a meadow in his garden. He divides it into N * M squares. Initially all the squares were covered with grass. He mowed down the grass on some of the squares and thinks the meadow is beautiful if and only if 1. Not all squares are covered with grass. 2. No two mowed squares are adjacent. Two squares are adjacent if they share an edge. Here comes the problem: Is Tom‘s meadow beautiful now?

Input

Output

Sample Input

2 2
1 0
0 1
2 2
1 1
0 0
2 3
1 1 1
1 1 1
0 0

Sample Output

Yes
No
No

问题分析：

Tom有一块草坪，分成N*M个区域，有修剪过的草坪和未修剪过的草坪。求TOM的草坪漂不漂亮。

漂亮的条件：

①草坪不能全为未修剪过的草坪。

②相邻草坪不能同为修剪过的草坪。

代码如下：

</pre><pre name="code" class="cpp">#include <iostream>
#define MAX 12                                   //最大12格
using namespace std;
int map[MAX][MAX];
int a[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
int n,m,sum,mark;
bool Bound(int x,int y)
{
    return (x>=0&&y>=0&&x<n&&y<m);
}

void Decide()
{
    int i,j,ti,tj,k;
    for(i=0; i<n; i++)
        for(j=0; j<m; j++)                   //依次以每一个地区为原点向四周搜索
        {
            if(map[i][j]==1)                 //如果当前地区是未修减过的草坪，未修减草坪数sum++，结束当前循环
            {
                sum++;
                continue;
            }
            for(k=0; k<4; k++)
            {
                ti=i+a[k][0];
                tj=j+a[k][1];
                if(Bound(ti,tj))             //在给定范围内
                {
                    if(map[ti][tj]==0)       //邻边是修减过的草坪
                    {
                        mark=1;
                        return ;
                    }
                }
            }
        }
}

int main()
{
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        int i,j;
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                cin>>map[i][j];
        mark=0;
        sum=0;
        Decide();
        if(mark==1||sum==m*n)                 //如果不满足条件1和条件2，输出No
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
    return 0;
}

学习心得：

这是我碰到的比较简单的搜索问题了，之前那些走迷宫的真心晕，，虽然借鉴了下别人的分析，但好在自己成功做了出来。

YTUOJ-Beautiful Meadow

原文：http://blog.csdn.net/liuchang54/article/details/45599239