CF980B Marlin 构造思维二十四

Marlin

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The city of Fishtopia can be imagined as a grid of 44 rows and an odd number of columns. It has two main villages; the first is located at the top-left cell (1,1)(1,1), people who stay there love fishing at the Tuna pond at the bottom-right cell (4,n)(4,n). The second village is located at (4,1)(4,1) and its people love the Salmon pond at (1,n)(1,n).

The mayor of Fishtopia wants to place kk hotels in the city, each one occupying one cell. To allow people to enter the city from anywhere, hotels should not be placed on the border cells.

A person can move from one cell to another if those cells are not occupied by hotels and share a side.

Can you help the mayor place the hotels in a way such that there are equal number of shortest paths from each village to its preferred pond?

Input

The first line of input contain two integers, nn and kk (3≤n≤993≤n≤99, 0≤k≤2×(n−2)0≤k≤2×(n−2)), nn is odd, the width of the city, and the number of hotels to be placed, respectively.

Output

Print "YES", if it is possible to place all the hotels in a way that satisfies the problem statement, otherwise print "NO".

If it is possible, print an extra 44 lines that describe the city, each line should have nn characters, each of which is "#" if that cell has a hotel on it, or "." if not.

Examples

input

Copy

7 2

output

Copy

YES
.......
.#.....
.#.....
.......

input

Copy

5 3

output

Copy

YES
.....
.###.
.....
.....

题意：现在有一个4*n的地图，a村庄的人在（1，1），他们要去（4，n），b村庄的人在（4，1），他们要去（1，n），路途的中间有m个酒店，村民不能经过酒店。问怎么设置酒店可以使a、b村庄的人到目的地的最短路大小相同。

题解：通过一番枚举验证，发现只要酒店能关于x轴或者y轴对称，就能满足条件。

然后对比样例，我们不难发现，m使偶数关于x轴对称，为奇数关于y轴对称。

接下来就是按照上面说的构造这样的一个4*n的地图，构造奇数的情况的时候小心一点就行。

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 1e2 + ;

const int mod = 1e9 + ;

typedef long long ll;

char mapn[maxn][maxn];

int main(){

    std::ios::sync_with_stdio(false);

    ll n, m;

    cin >> n >> m;

    cout << "YES" << endl;

    for( ll i = ; i <= ; i ++ ) {

        for( ll j = ; j <= n; j ++ ) {

            mapn[i][j] = '.';

        }

    }

    if( m %  ==  ) {

        for( ll i = ; i <= ; i ++ ) {

            for( ll j = ; j <= +m/; j ++ ) {

                mapn[i][j] = '#';

            }

        }

    } else {

        ll t = ( n+ ) / , num = m; //奇数对称的中心点纵坐标是t，num不大于1时不用再填充了，大于1时关于t对称填充

        for( ll i = ; i <= ( (m-) / (n-) ) +  && num > ; i ++ ) {

            for( ll j = ; j <= t- && num > ; j ++ ) {

                mapn[i][t-j] = mapn[i][t+j] = '#';

                num -= ;

            }

        }

        mapn[][t] = '#';

    }

    for( ll i = ; i <= ; i ++ ) {

        for( ll j = ; j <= n; j ++ ) {

            cout << mapn[i][j];

        }

        cout << endl;

    }

    return ;

}

巴特西

CF980B Marlin 构造思维二十四

最新文章

热门文章

巴特西

CF980B Marlin 构造 思维 二十四

最新文章

热门文章

CF980B Marlin 构造思维二十四