276 条题解
-
-1
xudf6 LV 8 @ 2017-04-08 20:01:03
/*简单DFS，DFS的同时把#标记为-，这样扫一遍过去，启动DFS的次数就是答案。*/ #include <cstdio> int n,m; char g[120][120]; void dfs(int x, int y) { if (x < 0 || x >=n || y < 0 || y >= m || g[x][y]=='-') return; g[x][y] = '-'; for (int dx = -1; dx<=1;dx++) for (int dy = -1; dy<=1;dy++) dfs(x+dx,y+dy);//八个方向的DFS int dx2[]={-2,2,0,0}, dy2[]={0,0,-2,2}; for (int i = 0; i < 4; i++) dfs(x+dx2[i],y+dy2[i]);//四个垂直，距离为2的DFS } int main() { scanf("%d%d",&n,&m); for (int i = 0; i < n; i++) scanf("%s",g[i]); int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (g[i][j] == '#') { ans++; dfs(i,j); } } printf("%d\n",ans); } -
-1
include <iostream>
include <cstdio>
include <cstring>
using namespace std;
const int MAXN=105;
int n,m,COUNT;
char M[MAXN][MAXN];
int dx[12]={-2,-1,-1,-1,0,0,0,0,1,1,1,2};
int dy[12]={0,-1,0,1,-2,-1,1,2,-1,0,1,0};
void Init()
{
COUNT=0;
for(int i=0;i<n;i++)
scanf("%s",M[i]);
//for(int i=0;i<n;i++)
// printf("%s\n",M[i]);
}
void dfs(int x,int y)
{
M[x][y]='-';
for(int i=0;i<12;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m)
if(M[nx][ny]=='#')
dfs(nx,ny);
}
}
void Solve()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(M[i][j]=='#')
{
COUNT++;
dfs(i,j);
}
}
printf("%d\n",COUNT);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
Init();
Solve();
}
return 0;
} -
-1
#include <iostream> #include <cstdlib> #include <cstdio> #include <climits> #include <cmath> #include <algorithm> #include <functional> #include <iterator> #include <cstring> #include <set> #include <vector> #include <queue> #include <list> #include <cctype> #include <string> #include <sstream> #include <stack> #include <utility> using namespace std; char sky[105][105]; int visited[105][105]; int dx[]={-2,-1,-1,-1,0,0,0,0,1,1,1,2}; int dy[]={0,-1,0,1,-2,-1,1,2,-1,0,1,0}; int sum=0; //_________________________________________ int main() { int n,m; cin>>n>>m; memset(visited,0,sizeof(visited)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin>>sky[i][j]; } } //____________________________________________ for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if(visited[i][j]==0 && sky[i][j]=='#') //找到一个发光的没访问的节点，说明多了一个图案 { //利用BFS把这个图案的所有点标记为已访问 sum++; visited[i][j]=1; pair<int,int> st[12000]; int head=0; int tail=1; st[head].first=i;st[head].second=j; while (head<tail) { for(int d=0;d<=11;d++) { int x=st[head].first+dx[d];int y=st[head].second+dy[d]; if(x>=1 && x<=n && y>=1 && y<=m && visited[x][y]==0 && sky[x][y]=='#') { visited[x][y]=1; st[tail].first=x;st[tail].second=y; tail++; } } head++; } } } } //__________________________________________________ cout<<sum; return 0; } -
-1
#include<bits/stdc++.h> using namespace std; char a[105][105]; bool b[105][105]; int m,n; int x1[]={1,-1,2,-2,0,0,0,0,1,1,-1,-1}; int y2[]={0,0,0,0,1,-1,2,-2,1,-1,1,-1}; void find(int x,int y) { b[x][y]=true; int i,xx,xy; for(i=0;i<12;i++) { xx=x+x1[i]; xy=y+y2[i]; if(xx>=0 && xx<n && xy>=0 && xy<m &&! b[xx][xy] && a[xx][xy]=='#') find(xx,xy); } return; } int main() { memset(b,0,sizeof(b)); cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j]; int i,j,ans=0; for(i=0;i<n;i++) for(j=0;j<m;j++) if(a[i][j]=='#' && !b[i][j] ) { find(i,j); ans++; } cout<<ans; return 0; } -
-1
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define mod 10002
using namespace std;
int n,m,map[102][102],mark[102][102],ct;
int qx[10002],qy[10002];
int xx[12]={-2,-1,-1,-1,0,0,0,0,1,1,1,2},
yy[12]={0,-1,0,1,-2,-1,1,2,-1,0,1,0};
void init()
{
scanf("%d%d",&n,&m);
int i,j;
char ch[105];
for(i=0;i<n;i++)
{scanf("%s",ch);
for(j=0;j<m;j++)
{if(ch[j]=='-') map[i][j]=0;
else map[i][j]=1;
}
}
}
bool check(int x,int y)
{
if(x<0||x>=n||y<0||y>=m||map[x][y]==0) return false;
if(map[x][y]==1&&mark[x][y]) return false;
return true;
}
void bfs(int sx,int sy)
{
int t=0,w=1,i,xt,yt,x,y;
qx[0]=sx; qy[0]=sy;
while(t!=w)
{x=qx[t], y=qy[t]; t=(t+1)%mod;
for(i=0;i<12;i++)
{xt=x+xx[i]; yt=y+yy[i];
if(check(xt,yt))
{mark[xt][yt]=ct; qx[w]=xt; qy[w]=yt; w=(w+1)%mod;}
}
}
}
void work()
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{if(map[i][j]&&!mark[i][j])
{ct++; bfs(i,j);}
}
}
int main()
{
init(); work();
printf("%d\n",ct);
return 0;
} -
-1
虽说tag有搜索但我就用并查集
2016.11.15修改:*1000改为<<10,去除debug用语句
编译成功
Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(48,20) Warning: Variable "isus" does not seem to be initialized
Linking foo.exe
53 lines compiled, 0.0 sec, 28208 bytes code, 1316 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 5716 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5712 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5712 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 5712 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 5720 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 5716 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 5712 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 5712 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 5716 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 5712 KiB, score = 10
Accepted, time = 15 ms, mem = 5720 KiB, score = 100
代码
```pascal
{$inline on}
const zb:array[1..6,0..1] of longint=((0,1),(0,2),(1,1),(1,0),(1,-1),(2,0));
var n,m,i,j,k,ans,t:longint;tempc:char;isf:boolean;
map:array[-2..102,-2..102] of boolean;
//ufs:array[-2..102,-2..102] of longint;
isus:array[1..1000000] of boolean;
ufs:array[1..1000000] of longint;function sf(k:longint):longint;
begin
if ufs[k]=k then exit(k);
sf:=sf(ufs[k]);ufs[k]:=sf;
end;procedure union(x,y:longint);inline;
begin
x:=sf(x);y:=sf(y);ufs[x]:=y;
end;function judge(x,y:longint):boolean;inline;
begin
x:=sf(x);y:=sf(y);
exit(x=y);
end;function tolo(a,b:longint):longint;inline;
begin exit(a<<10+b);end;begin
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do begin
ufs[tolo(i,j)]:=tolo(i,j);isf:=true;
read(tempc);
map[i,j]:=tempc='#';
if map[i,j] then for k:=1 to 6 do
if map[i-zb[k,0],j-zb[k,1]] then
if isf then begin
isf:=false;union(ufs[tolo(i,j)],ufs[tolo(i-zb[k,0],j-zb[k,1])]);
end else union(ufs[tolo(i-zb[k,0],j-zb[k,1])],ufs[tolo(i,j)]);
end;
readln;
end;
ans:=0;
for i:=1 to n do
for j:=1 to m do if map[i,j] then begin
t:=sf(ufs[tolo(i,j)]);
if not isus[t] then begin
inc(ans);isus[t]:=true;
end;
end;writeln(ans);
end.
``` -
-1
zhaoyunhan LV 8 @ 2016-10-05 15:26:04
#include <stdio.h>
#include <math.h>
#include<algorithm>
using namespace std;
int n,m,cnt;
char a[105][105];
void dfs(int i,int j)
{
int dx,dy,x,y;
a[i][j]='-';
for(dx=-2;dx<=2;dx++)
{
for(dy=-2;dy<=2;dy++)
{
if(abs(dx)+abs(dy)<=2)
{
x=i+dx;
y=j+dy;
if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='#')
dfs(x,y);
}
}
}
return;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
getchar();
for(i=0; i<n; i++)
{
gets(a[i]);
}
for(i=0; i<n; i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]=='#')
{
dfs(i,j);
cnt++;
}
}
}
printf("%d\n",cnt);
return 0;
} -
-1
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;int n,m,t;
bool b[105][105];
char c[105][105];void bb(int i,int j)
{
b[i][j]=0;
if (b[i-1][j-1]==1) bb(i-1,j-1);
if (b[i-1][j]==1) bb(i-1,j);
if (b[i-1][j+1]==1) bb(i-1,j+1);
if (b[i][j-1]==1) bb(i,j-1);
if (b[i][j+1]==1) bb(i,j+1);if ((j-2)>=0)
{if (b[i][j-2]==1) bb(i,j-2);}
if (b[i][j+2]==1) bb(i,j+2);
if (b[i+1][j-1]==1) bb(i+1,j-1);
if (b[i+1][j]==1) bb(i+1,j);
if (b[i+1][j+1]==1) bb(i+1,j+1);if ((i-2)>=0)
{if (b[i-2][j]==1) bb(i-2,j);}
if (b[i+2][j]==1) bb(i+2,j);
}int main()
{
int i,j;scanf("%d %d",&n,&m);
for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
{
scanf("%c",&c[i][j]);
if (c[i][j]=='#') b[i][j]=1;
else b[i][j]=0;
}for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
{
if (b[i][j]==1)
{
t++;
bb(i,j);
}
}printf("%d\n",t);
return 0;
}
你们这些渣渣，我小学二年级都做得出来 -
-1
#include <iostream> #include <cstdlib> #include <cstring> int dx[13]={0,1,2,-1,-2,0,0,0,0,1,-1,1,-1}; int dy[13]={0,0,0,0,0,1,2,-1,-2,1,1,-1,-1}; int total,m,n; char a[101][101]; using namespace std; void search(int x,int y) { int i,p,q; a[x][y]='-'; for(i=1; i<=12; i++) { p=x+dx[i]; q=y+dy[i]; if(a[p][q]=='#'&&p>0&&p<=m&&q>0&&q<=n) { search(p,q); } } return; } int main() { // freopen("test.in","r",stdin); int i,j,p,q; cin>>m>>n; // fill(*a,*a + m * n, '.'); for(i=1; i<=m; i++) for(j=1; j<=n; j++) cin>>a[i][j]; for(i=1; i<=m; i++) for(j=1; j<=n; j++) { if(a[i][j]=='#') { search(i,j); total++; } } cout<<total; return 0; }友情题目：POJ 2386 :Lake counting.
-
-1
#include<iostream> #include<cstdio> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[1000][1000],n,m,b[200000],p=0,c[200000],ans=0; char w; void search(int m,int s) { if(a[m][s+1]==1){a[m][s+1]=0;search(m,s+1);} if(a[m][s-1]==1){a[m][s-1]=0;search(m,s-1);} if(a[m+1][s]==1){a[m+1][s]=0;search(m+1,s);} if(a[m-1][s]==1){a[m-1][s]=0;search(m-1,s);} if(a[m+1][s+1]==1){a[m+1][s+1]=0;search(m+1,s+1);} if(a[m-1][s+1]==1){a[m-1][s+1]=0;search(m-1,s+1);} if(a[m+1][s-1]==1){a[m+1][s-1]=0;search(m+1,s-1);} if(a[m-1][s-1]==1){a[m-1][s-1]=0;search(m-1,s-1);} if(a[m][s+2]==1){a[m][s+2]=0;search(m,s+2);} if(a[m][s-2]==1){a[m][s-2]=0;search(m,s-2);} if(a[m+2][s]==1){a[m+2][s]=0;search(m+2,s);} if(a[m-2][s]==1){a[m-2][s]=0;search(m-2,s);} } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>w;if(w=='#'){p++;a[i][j]=1;b[p]=i;c[p]=j;} else a[i][j]=0; } //for(int i=1;i<=p;i++) // cout<<b[i]<<" "<<c[i]<<endl; for(int i=1;i<=p;i++) if(a[b[i]][c[i]]==1) {ans++; search(b[i],c[i]); }cout<<ans<<endl; return 0; } -
-1
BFS
#include"stdio.h"
#include"stdlib.h"
#include"queue"
#include"string.h"
using namespace std;
typedef long long ll;
int dir[12][2]={{0,2},{0,-2},{2,0},{-2,0},{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{-1,0},{0,1},{0,-1}};
int n;
int visit[100+10][100+10];
char g[100+10][100+10];
int r,c;
int check(int nx,int ny)
{
return nx>=0&&nx<r&&ny>=0&&ny<c&&g[nx][ny]=='#'&&visit[nx][ny]==0;
}
void dfs(int si,int sj)
{
visit[si][sj]=1;
int i;
for(i=0;i<12;i++)
{
int nx=si+dir[i][0];
int ny=sj+dir[i][1];
if(check(nx,ny))
{
visit[nx][ny]=1;
dfs(nx,ny);
}
}}
void bfs(int si,int sj)
{
queue<pair<int,int> >Q;
Q.push(make_pair(si,sj));
visit[si][sj]=1;
while(!Q.empty())
{
pair<int,int> u=Q.front();Q.pop();
for(int i=0;i<12;i++)
{
int nx=u.first+dir[i][0];
int ny=u.second+dir[i][1];
if(check(nx,ny))
{
Q.push(make_pair(nx,ny));
visit[nx][ny]=1;
}}
}
}
int main()
{int i;
while(scanf("%d%d",&r,&c)==2)
{
getchar();
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
g[i][j]=getchar();
getchar();
}
int ans=0;
memset(visit,0,sizeof(visit));
/*
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(check(i,j))
{
dfs(i,j);
ans++;
}
*/
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(check(i,j))
{
bfs(i,j);
ans++;
}
printf("%d\n",ans);
}
return 0;
} -
-1
DFS
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef long long ll;
int dir[12][2]={{0,2},{0,-2},{2,0},{-2,0},{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{-1,0},{0,1},{0,-1}};
int n;
int visit[100+10][100+10];
char g[100+10][100+10];
int r,c;
int check(int nx,int ny)
{
return nx>=0&&nx<r&&ny>=0&&ny<c&&g[nx][ny]=='#'&&visit[nx][ny]==0;
}
void dfs(int si,int sj)
{
visit[si][sj]=1;
int i;
for(i=0;i<12;i++)
{
int nx=si+dir[i][0];
int ny=sj+dir[i][1];
if(check(nx,ny))
{
visit[nx][ny]=1;
dfs(nx,ny);
}
}}
int main()
{int i;
while(scanf("%d%d",&r,&c)==2)
{
getchar();
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
g[i][j]=getchar();
getchar();
}
int ans=0;
memset(visit,0,sizeof(visit));
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(check(i,j))
{
dfs(i,j);
ans++;
}
printf("%d\n",ans);
}
return 0;
} -
-1
#include <cstdio> #include <functional> #include <cstring> #include <iostream> using namespace std; const int dx[12] = {0, 1, 1, 1, 0, -1, -1, -1, 0, 2, 0, -2}, dy[12] = {1, 0, 1, -1, -1, -1, 1, 0, 2, 0, -2, 0}; int n, m, ans = 0; string s; bool v[101][101]; int main() { scanf("%d%d", &n, &m); memset(v, 0, sizeof(v)); for(int i = 1; i <= n; i++) { cin >> s; for(int j = 0; j < m; j++) if(s[j] == '-') { v[i][j + 1] = true; } } function<void(int x, int y)> dfs; dfs = ([&] (int x, int y) { if(v[x][y]) { return; } v[x][y] = true; for(int i = 0; i < 12; i++) if(x + dx[i] < 1 || x + dx[i] > n || y + dy[i] < 1 || y + dy[i] > m) { continue; } else { dfs(x + dx[i], y + dy[i]); } }); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(v[i][j] == false) { dfs(i, j); ans++; } printf("%d", ans); }论如何用C++11使程序变得晦涩难懂
-
-1
/*********************无脑深搜************************/
#include<iostream> #include<cstdio> using namespace std; int n,m,ans; int map[110][110]={0}; int visit[110][110]={0}; void dfs(int x,int y){ if(map[x][y-2]==1&&visit[x][y-2]==0){ visit[x][y-2]=1; dfs(x,y-2); } if(map[x][y-1]==1&&visit[x][y-1]==0){ visit[x][y-1]=1; dfs(x,y-1); } if(map[x+1][y-1]==1&&visit[x+1][y-1]==0){ visit[x+1][y-1]=1; dfs(x+1,y-1); } if(map[x-1][y-1]==1&&visit[x-1][y-1]==0){ visit[x-1][y-1]=1; dfs(x-1,y-1); } if(map[x+2][y]==1&&visit[x+2][y]==0){ visit[x+2][y]=1; dfs(x+2,y); } if(map[x+1][y]==1&&visit[x+1][y]==0){ visit[x+1][y]=1; dfs(x+1,y); } if(map[x-1][y]==1&&visit[x-1][y]==0){ visit[x-1][y]=1; dfs(x-1,y); } if(map[x-2][y]==1&&visit[x-2][y]==0){ visit[x-2][y]=1; dfs(x-2,y); } if(map[x-1][y+1]==1&&visit[x-1][y+1]==0){ visit[x-1][y+1]=1; dfs(x-1,y+1); } if(map[x+1][y+1]==1&&visit[x+1][y+1]==0){ visit[x+1][y+1]=1; dfs(x+1,y+1); } if(map[x][y+1]==1&&visit[x][y+1]==0){ visit[x][y+1]=1; dfs(x,y+1); } if(map[x][y+2]==1&&visit[x][y+2]==0){ visit[x][y+2]=1; dfs(x,y+2); } return; } int main(){ char c; int i,j; cin>>n>>m; for(i=2;i<=n+1;i++){ for(j=2;j<=m+1;j++){ cin>>c; if(c=='#') map[i][j]=1; } } for(i=2;i<=n+1;i++){ for(j=2;j<=m+1;j++){ if(map[i][j]==1&&visit[i][j]==0){ ans++; dfs(i,j); } } } printf("%d",ans); return 0; } -
-1
你们都用的广搜，那我发个深搜的吧
include <stdio.h>
include <math.h>
int n, m, cnt;
char a[105][105];void dfs(int i, int j)
{
int dx, dy, x, y;
a[i][j] = '-';
for (dx=-2; dx<=2; dx++) {
for (dy=-2; dy<=2; dy++) {
if (abs(dx) + abs(dy) <= 2) {
x = i+dx;
y = j+dy;
if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == '#')
dfs(x,y);
}
}
}
return ;
}int main (void)
{
int i, j;
scanf("%d%d",&n,&m);
getchar();
for (i=0; i<n; i++) {
gets(a[i]);
}
for (i=0; i<n; i++) {
for (j=0; j<m; j++) {
if (a[i][j] == '#') {
dfs(i,j);
cnt++;
}
}
}
printf("%d\n",cnt);
return 0;
}
xudf6
LV 8
@ 2017-04-08 20:01:03
信息
- ID
- 1051
- 难度
- 4
- 分类
- 搜索 | 搜索与剪枝 点击显示
- 标签
- 递交数
- 6196
- 已通过
- 2431
- 通过率
- 39%
- 被复制
- 13
- 上传者
-
Vivian Snow
