Ural 1250 Sea Burial 题解

发表于 更新于 分类于 ，
本文字数： 13k 阅读时长 ≈ 12 分钟

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)

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

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

程序

  1. BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    // #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**************************************************************/

  2. DFS(与BFS十分类似)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    // #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$了。

__EOF__