Ural 1250 Sea Burial 题解

程序员文章站 2022-06-19 19:07:52

Ural 1250 Sea Burial 题解 [TOC] 题意给定一个$n\times m$的地图，$.$为水，$\ $为陆，地图的外部是水(地图被水包围)。水为八连通，陆为四联通。联通的水称为海，联通的陆称为岛。海内可能有岛，岛内可能有海。给定$x,y$求在包含$(x,y)$(保证$(x,y) ......

ural 1250 sea burial 题解

ural 1250 sea burial 题解

题意

给定一个$n\times m$的地图，$.$为水，$\#$为陆，地图的外部是水(地图被水包围)。水为八连通，陆为四联通。联通的水称为海，联通的陆称为岛。海内可能有岛，岛内可能有海。给定$x,y$求在包含$(x,y)$(保证$(x,y)$为水)的海里面有多少岛。

输入

第一行包含$m,n,y,x(1\le n,m\le 500,1\le x \le n,1\le y \le m)$

以下若干行为一个$n\times m$的地图

题解

考虑bfs或dfs(以下简称bfs)

从$(x,y)$bfs，找出包含$(x,y)$的海。
从地图外部(水)bfs，找出在包含$(x,y)$的海的外面部分。
执行完前两步，就可以知道包含$(x,y)$的海里面的部分，数出包含$(x,y)$的海里面的部分有多少岛即可。

tip: 运用二进制可以使程序简便。记陆为$1$，岛为$2$。设我们需要的值为$x$，当前的值为$y$，只需判断$(x\&y)$是否大于$0$即可。第1步时$x=2$，第2步时$x=3$(想一想，为什么，答案最后揭晓)，第3步时$x=1$。

程序

// #pragma gcc optimize(2)
// #pragma g++ optimize(2)
// #pragma comment(linker,"/stack:102400000,102400000")

// #include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <array>
#include <cfenv>
#include <cmath>
#include <ctime>
#include <deque>
#include <mutex>
#include <queue>
#include <ratio>
#include <regex>
#include <stack>
#include <tuple>
#include <atomic>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <chrono>
#include <cstdio>
#include <cwchar>
#include <future>
#include <limits>
#include <locale>
#include <memory>
#include <random>
#include <string>
#include <thread>
#include <vector>
#include <cassert>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ctgmath>
#include <cwctype>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ccomplex>
#include <cstdbool>
#include <iostream>
#include <typeinfo>
#include <valarray>
#include <algorithm>
#include <cinttypes>
#include <cstdalign>
#include <stdexcept>
#include <typeindex>
#include <functional>
#include <forward_list>
#include <system_error>
#include <unordered_map>
#include <unordered_set>
#include <scoped_allocator>
#include <condition_variable>
// #include <conio.h>
// #include <windows.h>
using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double ld;
typedef pair<int,int> pii;
#if (win32) || (win64) || (__win32) || (__win64) || (_win32) || (_win64) || (windows)
#define lld "%i64d"
#define llu "%i64u"
#else
#define lld "%lld"
#define llu "%llu"
#endif
#define ui(n) ((unsigned int)(n))
#define ll(n) ((long long)(n))
#define ull(n) ((unsigned long long)(n))
#define fl(n) ((float)(n))
#define ld(n) ((double)(n))
#define ld(n) ((long double)(n))
#define char(n) ((char)(n))
#define bool(n) ((bool)(n))
#define fixpoint(n) fixed<<setprecision(n)

const int inf=1061109567;
const int ninf=-1044266559;
const ll linf=4557430888798830399;
const ld eps=1e-15;
#define mod (1000000007)
#define pi (3.1415926535897932384626433832795028841971)

/*
#define mb_len_max 5
#define shrt_min (-32768)
#define shrt_max 32767
#define ushrt_max 0xffffu
#define int_min (-2147483647 - 1)
#define int_max 2147483647
#define uint_max 0xffffffffu
#define long_min (-2147483647l - 1)
#define long_max 2147483647l
#define ulong_max 0xfffffffful
#define llong_max 9223372036854775807ll
#define llong_min (-9223372036854775807ll - 1)
#define ullong_max 0xffffffffffffffffull
*/

#define mp make_pair
#define mt make_tuple
#define all(a) (a).begin(),(a).end()
#define pall(a) (a).rbegin(),(a).rend()
#define log2(x) log(x)/log(2)
#define log(x,y) log(x)/log(y)
#define sz(a) ((int)(a).size())
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define rep1(i,n) for(int i=1;i<=((int)(n));i++)
#define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++)
#define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++)
#define repd(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define repd1(i,n) for(int i=((int)(n));i>=1;i--)
#define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--)
#define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--)
#define for(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step)))
#define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
#define repv(i,v) for(auto i:v)
#define repe(i,v) for(auto &i:v)
#define ms(x,y) memset(x,y,sizeof(x))
#define mc(x) ms(x,0)
#define minf(x) ms(x,63)
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define sqr(x) ((x)*(x))
#define un(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define filein(x) freopen(x,"r",stdin)
#define fileout(x) freopen(x,"w",stdout)
#define fileio(x)\
    freopen(x".in","r",stdin);\
    freopen(x".out","w",stdout)
#define filein2(filename,name) ifstream name(filename,ios::in)
#define fileout2(filename,name) ofstream name(filename,ios::out)
#define file(filename,name) fstream name(filename,ios::in|ios::out)
#define pause system("pause")
#define cls system("cls")
#define fs first
#define sc second
#define pc(x) putchar(x)
#define gc(x) x=getchar()
#define endl pc('\n')
#define sf scanf
#define pf printf

inline int read()
{
    int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}

inline ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}
inline ll gcdll(ll a,ll b){return b?gcdll(b,a%b):a;}
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={1,0,-1,0,-1,-1,1,1};
/************************************************************begin************************************************************/
const int maxn=510;

int n,m,x,y,s[maxn][maxn],ans; // '#'=>1(01) '.'=>2(10)
bool vis[maxn][maxn];

inline void bfs(int sx,int sy,int status)
{
    vis[sx][sy]=1;
    queue<pair<int,int> > q;q.push({sx,sy});

    while(!q.empty())
    {
        int x=q.front().fs,y=q.front().sc;q.pop();

        rep(i,8)
        {
            if(s[x][y]==1&&i>3) break;

            int cx=x+dx[i],cy=y+dy[i];
            if(cx>0&&cx<=n&&cy>0&&cy<=m&&!vis[cx][cy]&&(s[cx][cy]&status))
            {
                vis[cx][cy]=1;
                q.push({cx,cy});
            }
        }
    }
}

int main()
{
    cin>>m>>n>>y>>x;
    rep1(i,n) rep1(j,m)
    {
        char c;cin>>c;
        s[i][j]=(c=='#'?1:2);
    }
    
    // step 1
    bfs(x,y,2);
    
    // step 2
    rep1(i,n)
    {
        bfs(i,0,3);
        bfs(i,m+1,3);
    }
    rep1(j,m)
    {
        bfs(0,j,3);
        bfs(n+1,j,3);
    }
    
    //step 3
    rep1(i,n) rep1(j,m) if(!vis[i][j]&&s[i][j]==1)
    {
        ans++;
        bfs(i,j,1);
    }

    cout<<ans;

    return 0;
}
/*************************************************************end**************************************************************/

dfs(与bfs十分类似)

// #pragma gcc optimize(2)
// #pragma g++ optimize(2)
// #pragma comment(linker,"/stack:102400000,102400000")

// #include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <array>
#include <cfenv>
#include <cmath>
#include <ctime>
#include <deque>
#include <mutex>
#include <queue>
#include <ratio>
#include <regex>
#include <stack>
#include <tuple>
#include <atomic>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <chrono>
#include <cstdio>
#include <cwchar>
#include <future>
#include <limits>
#include <locale>
#include <memory>
#include <random>
#include <string>
#include <thread>
#include <vector>
#include <cassert>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ctgmath>
#include <cwctype>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ccomplex>
#include <cstdbool>
#include <iostream>
#include <typeinfo>
#include <valarray>
#include <algorithm>
#include <cinttypes>
#include <cstdalign>
#include <stdexcept>
#include <typeindex>
#include <functional>
#include <forward_list>
#include <system_error>
#include <unordered_map>
#include <unordered_set>
#include <scoped_allocator>
#include <condition_variable>
// #include <conio.h>
// #include <windows.h>
using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double ld;
typedef pair<int,int> pii;
#if (win32) || (win64) || (__win32) || (__win64) || (_win32) || (_win64) || (windows)
#define lld "%i64d"
#define llu "%i64u"
#else
#define lld "%lld"
#define llu "%llu"
#endif
#define ui(n) ((unsigned int)(n))
#define ll(n) ((long long)(n))
#define ull(n) ((unsigned long long)(n))
#define fl(n) ((float)(n))
#define ld(n) ((double)(n))
#define ld(n) ((long double)(n))
#define char(n) ((char)(n))
#define bool(n) ((bool)(n))
#define fixpoint(n) fixed<<setprecision(n)

const int inf=1061109567;
const int ninf=-1044266559;
const ll linf=4557430888798830399;
const ld eps=1e-15;
#define mod (1000000007)
#define pi (3.1415926535897932384626433832795028841971)

/*
#define mb_len_max 5
#define shrt_min (-32768)
#define shrt_max 32767
#define ushrt_max 0xffffu
#define int_min (-2147483647 - 1)
#define int_max 2147483647
#define uint_max 0xffffffffu
#define long_min (-2147483647l - 1)
#define long_max 2147483647l
#define ulong_max 0xfffffffful
#define llong_max 9223372036854775807ll
#define llong_min (-9223372036854775807ll - 1)
#define ullong_max 0xffffffffffffffffull
*/

#define mp make_pair
#define mt make_tuple
#define all(a) (a).begin(),(a).end()
#define pall(a) (a).rbegin(),(a).rend()
#define log2(x) log(x)/log(2)
#define log(x,y) log(x)/log(y)
#define sz(a) ((int)(a).size())
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define rep1(i,n) for(int i=1;i<=((int)(n));i++)
#define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++)
#define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++)
#define repd(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define repd1(i,n) for(int i=((int)(n));i>=1;i--)
#define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--)
#define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--)
#define for(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step)))
#define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
#define repv(i,v) for(auto i:v)
#define repe(i,v) for(auto &i:v)
#define ms(x,y) memset(x,y,sizeof(x))
#define mc(x) ms(x,0)
#define minf(x) ms(x,63)
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define sqr(x) ((x)*(x))
#define un(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define filein(x) freopen(x,"r",stdin)
#define fileout(x) freopen(x,"w",stdout)
#define fileio(x)\
    freopen(x".in","r",stdin);\
    freopen(x".out","w",stdout)
#define filein2(filename,name) ifstream name(filename,ios::in)
#define fileout2(filename,name) ofstream name(filename,ios::out)
#define file(filename,name) fstream name(filename,ios::in|ios::out)
#define pause system("pause")
#define cls system("cls")
#define fs first
#define sc second
#define pc(x) putchar(x)
#define gc(x) x=getchar()
#define endl pc('\n')
#define sf scanf
#define pf printf

inline int read()
{
    int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}

inline ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}
inline ll gcdll(ll a,ll b){return b?gcdll(b,a%b):a;}
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={1,0,-1,0,-1,-1,1,1};
/************************************************************begin************************************************************/
const int maxn=510;

int n,m,x,y,s[maxn][maxn],ans; // '#'=>1(01) '.'=>2(10)
bool vis[maxn][maxn];

inline void dfs(int x,int y,int status)
{
    vis[x][y]=1;

    rep(i,8)
    {
        if(s[x][y]==1&&i>3) break;

        int cx=x+dx[i],cy=y+dy[i];
        if(cx>0&&cx<=n&&cy>0&&cy<=m&&!vis[cx][cy]&&(s[cx][cy]&status)) dfs(cx,cy,status);
    }
}

int main()
{
    cin>>m>>n>>y>>x;
    rep1(i,n) rep1(j,m)
    {
        char c;cin>>c;
        s[i][j]=(c=='#'?1:2);
    }
    
    // step 1
    dfs(x,y,2);
    
    // step 2
    rep1(i,n)
    {
        dfs(i,0,3);
        dfs(i,m+1,3);
    }
    rep1(j,m)
    {
        dfs(0,j,3);
        dfs(n+1,j,3);
    }
    
    //step 3
    rep1(i,n) rep1(j,m) if(!vis[i][j]&&s[i][j]==1)
    {
        ans++;
        dfs(i,j,1);
    }

    cout<<ans;

    return 0;
}
/*************************************************************end**************************************************************/

tip's answer: 第2步是需要找出在包含$(x,y)$的海的外面部分，而外面部分不分海陆，$x=3$即$x=(11)_2$，这样$1\&3$与$2\&3$都大于$0$了。

上一篇： [Go] golang的MPG调度模型

下一篇：奥尔良鸡腿煮着吃，快来get一下吧！