Codeforces Round #168 (Div. 2) B. Convex Shape（BFS || 模拟）

sugarbliss

330507人浏览 · 2019-04-19 14:52:39

sugarbliss · 2019-04-19 14:52:39 发布

题目链接：https://codeforces.com/problemset/problem/275/B

题意：从任意一个黑格子到任意一个黑格子都可以互达，且方向变化不超过1次(只能走黑格子)。

模拟思路：从一个黑色格到任意一个黑色格看能否通过两种方式到达其他任意一个黑色格子。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
const int inf = 0x3f3f3f3f;
const int N = 3e5+7;

int n,m,x[N],y[N],cnt;
char s[50][50];

bool check(int x,int a1,int b1,int y,int a2,int b2)
{
	for(int i = min(a1,b1); i <= max(a1,b1); i++)
        if(s[x][i] != 'B') return 0;

	for(int i = min(a2,b2); i <= max(a2,b2); i++)
        if(s[i][y] != 'B') return 0;
	return 1;
}

int main()
{
    cin >> n >> m;
	for(int i = 0; i < n; i++)
    {
        cin >> s[i];
        for(int j = 0; j < m; j++)
            if(s[i][j] == 'B') x[++cnt] = i, y[cnt] = j;
    }
    for(int i = 1; i < cnt; i++)
        for(int j = i + 1; j <= cnt; j++)
        {
            if(check(x[i],y[i],y[j],y[j],x[i],x[j])) continue;
            if(check(x[j],y[i],y[j],y[i],x[i],x[j])) continue;
            cout << "NO";
            return 0;
        }
    cout << "YES";
    return 0;
}
/*
4 4
wbbw
wbbw
wbww
wbbw
*/

BFS思路：主要是方向传递问题，我们可以在搜索时直接搜一行或者一列，这样就避免了走S型路线导致答案错误。还有一种方法用vis[][]数组即标记点是否用过，并记录转弯的次数，并且只有Next次数大于等于Now次数才有可能入队。下面给出两种BFS代码。

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x, y, c, f;
}Now, Next, s;
int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
int vis[55][55];
char mp[55][55];
int n, m;
int check(int tx, int ty)
{
    if(tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] == 'B')
        return 1;
    return 0;
}
int bfs(int x, int y)
{
    memset(vis, 0, sizeof(vis));
    int ret = 1, k;
    s = (node){x, y, 0, -1};
    vis[x][y]  = 1;
    queue <node> q; q.push(s);

    while(!q.empty())
    {
        Now = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            Next.x = Now.x + dir[i][0];
            Next.y = Now.y + dir[i][1];
            Next.c = Now.c;
            if(Now.f == -1) Next.f = i;
            else if(Next.f != i)
                Next.f = i, Next.c = Now.c + 1;

            while(check(Next.x, Next.y) && Next.c < 2)
            {
                if(!vis[Next.x][Next.y])
                {
                    vis[Next.x][Next.y] = 1; ret++;
                    q.push(Next);
                }
                Next.x += dir[i][0];
                Next.y += dir[i][1];
            }
        }
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 0; i < n; i++)
        scanf("%s",mp[i]);
    int cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(mp[i][j] == 'B') cnt++;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(mp[i][j] == 'B')
                if(bfs(i, j) != cnt)
                    return puts("NO"), 0;
    puts("YES");
}
/*
5 5
WBBWW
BBBWW
BBBWW
BBBWW
BBBBB

4 4
WBBW
WBBW
WBWW
WBBW
*/

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x, y, c, f;
}Now, Next, s;
int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
int vis[55][55];
char mp[55][55];
int n, m, cnt, ans;

int bfs(int x, int y)
{
    memset(vis, -1, sizeof(vis));
    int ret = 1, k;
    s = (node){x, y, 0, -1};
    vis[x][y]  = 0;
    queue <node> q; q.push(s);

    while(!q.empty())
    {
        Now = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int tx = Now.x + dir[i][0];
            int ty = Now.y + dir[i][1];
            if((vis[tx][ty] == -1 || vis[tx][ty] >= Now.c) && mp[tx][ty] == 'B')
            {
                if(Now.f == -1 || Now.f == i)
                {
                    vis[tx][ty] = Now.c;
                    Next = (node){tx, ty, Now.c, i};
                    q.push(Next);
                }
                else if(Now.c < 1)
                {
                    vis[tx][ty] = Now.c + 1;
                    Next = (node){tx, ty, Now.c + 1, i};
                    q.push(Next);
                }
            }

        }
    }
    ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(vis[i][j] != -1) ans++;
    return ans != cnt;
}
int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 0; i < n; i++)
        scanf("%s",mp[i]);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(mp[i][j] == 'B') cnt++;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(mp[i][j] == 'B' && bfs(i, j))
                return puts("NO"), 0;

    puts("YES");
}
/*
5 5
WBBWW
BBBWW
BBBWW
BBBWW
BBBBB
YES
4 4
WBBW
WBBW
WBWW
WBBW
NO
*/