目录
- ural 1250 sea burial 题解
ural 1250 sea burial 题解
题意
给定一个(ntimes m)的地图,(.)为水,(#)为陆,地图的外部是水(地图被水包围)。水为八连通,陆为四联通。联通的水称为海,联通的陆称为岛。海内可能有岛,岛内可能有海。给定(x,y)求在包含((x,y))(保证((x,y))为水)的海里面有多少岛。
输入
第一行包含(m,n,y,x(1le n,mle 500,1le x le n,1le y le m))
以下若干行为一个(ntimes 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)。
程序
- 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 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)了。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602448.html