题解 - Vijos

0

kimicao LV 3 @ 2006-09-23 12:54:52

测试数据 01：答案正确... 0ms

├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：答案正确... 0ms

??????

0

蔬灰 LV 6 @ 2006-08-21 19:58:51

floodfill是什么怎么用？

还有，再问一句

dp是什么

dfs又是什么

最近很久没做了，生疏了

0

rushloo LV 3 @ 2006-06-27 16:08:12

floodfill就是种子染色法

俗称洪水灌溉法

哈哈~~

0

风的边缘 LV 3 @ 2006-06-02 23:57:27

floodfill是什么？

0

真圣灵骑士 LV 3 @ 2006-05-21 14:35:48

55555...

floodfill只能过两个点~！~！~

0

zhymaoiing LV 3 @ 2006-02-10 16:33:01

太简单的floodfill了

0

Coldwings LV 4 @ 2006-01-27 23:51:58

地球人都知道的方法..

FF

0

永恒の灵魂 LV 3 @ 2006-02-03 16:19:51

BFS.

（我咋就没想到floodfill嘞，笨死了）

-1

暗燚 LV 8 @ 2018-08-16 09:30:09

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ans,n,m,f[110][110];
char a[110][110];
int tx[]={0,0,1,-1,-1,1,-1,1,2,-2,0,0};
int ty[]={1,-1,0,0,-1,1,1,-1,0,0,2,-2};
void dfs(int x,int y,int k)
{
    int dx,dy;
    for(int i=0;i<=11;i++)
    {
        dx=x+tx[i];
        dy=y+ty[i];
        if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]=='#'&&f[dx][dy]==0)
        {
            f[dx][dy]=k;
            dfs(dx,dy,k);
        }
    }
    return;
}
int main()  
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            
            if(a[i][j]=='#'&&f[i][j]==0)
            {
                ans++;
                f[i][j]=ans;
                dfs(i,j,ans);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

-1

runner LV 8 @ 2018-04-15 11:24:56

明显的DFS求联通块，
不过我写着写着好像就成了BFS
```cpp
#include <iostream>
#include <vector>
using namespace std;

struct Pos{
int x,y;
Pos(int x,int y){
this->x = x;
this->y = y;
}
};

int n,m;
char a[101][101];
bool visited[101][101] = {false};
int mov[12][2] = {{1,0},{2,0},{1,1},{0,1},{0,2},{-1,1},{-1,0},{-2,0},{-1,-1},{0,-1},{0,-2},{1,-1}};

void dfs(Pos p){
int x = p.x;
int y = p.y;
int u,v;
for (int i = 0; i < 12; ++i) {
u = x + mov[i][0];
v = y + mov[i][1];
if(u<0 || v<0 || u>=n || v>=m || a[u][v] != '#' || visited[u][v])
continue;
visited[u][v] = true;
dfs(Pos(u,v));
}
}

int main()
{
cin >> n >> m;
string s;
vector<Pos> v;
for (int i = 0; i < n; ++i) {
cin >> s;
for (int j = 0; j < m; ++j) {
a[i][j] = s[j];
if(a[i][j] == '#'){
v.push_back(Pos(i,j));
}
}
}
int ans = 0;
for (int i = 0; i < v.size(); ++i) {
if(!visited[v[i].x][v[i].y]){
ans++;
dfs(v[i]);
}
}
cout << ans << endl;

return 0;
}
```

-1

backwords LV 8 @ 2018-03-10 20:14:49

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include <map>
#include <queue>
#include <cstring>
#include <sstream>
#include <stack>
using namespace std;

const int MAX = 101;
char graph[MAX][MAX];
int color[MAX][MAX];
// |
int dr[] = {1,-1,0,0,-2,2,0,0,1,-1,1,-1,2,-2,0,0};
int dc[] = {0,0,1,-1,0,0,2,-2,1,1,-1,-1,0,0,2,-2};
int m,n;

inline bool inside(int nr,int nc) {
return nr < m && nr >= 0 && nc < n && nc >= 0;
}

void dfs(int r,int c,int cnt) {
int nr,nc;
for(int i = 0; i < 16; ++i) {
nr = r + dr[i];
nc = c + dc[i];
if(inside(nr,nc) && !color[nr][nc] && graph[nr][nc] == '#') {
color[nr][nc] = cnt;
dfs(nr,nc,cnt);
}
}
}

int main(int argc, char const *argv[])
{
cin >> m >> n;
for(int i = 0; i < m; ++i) scanf("%s",graph[i]);
int cnt = 0;

memset(color,0,sizeof(color));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(!color[i][j] && graph[i][j] == '#')
dfs(i,j,++cnt);
}

}

cout << cnt << endl;
return 0;
}
//dfs floodfill模板题（刘汝佳紫书）

-1

l上弦月l LV 8 @ 2018-03-03 12:57:55

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
bool map[105][105];
int x[12] = {-2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2};//储存搜索范围 
int y[12] = {0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0};
int n, m, ans = 0;
struct node
{
    int x, y;
};
int main( )
{
    cin >> n >> m;
    char temp;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> temp;
            if (temp == '#')
               map[i][j] = true;
            else 
               map[i][j] = false;
        }
    queue <node> bfsQueue;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (map[i][j])
            {
                node tempNode;
                tempNode.x = i;
                tempNode.y = j;
                bfsQueue.push(tempNode);
                while (!bfsQueue.empty())
                {
                    node t = bfsQueue.front();
                    bfsQueue.pop();
                    for (int k = 0; k < 12; k++)
                        if (map[t.x + x[k]][t.y + y[k]] && (t.x + x[k]) > 0 && (t.x + x[k]) <= n && (t.y + y[k]) > 0 && (t.y + y[k]) <= m)
                        {
                            map[t.x + x[k]][t.y + y[k]] = false;
                            tempNode.x = t.x + x[k];
                            tempNode.y = t.y + y[k];
                            bfsQueue.push(tempNode);
                        }
                }
                ans++;
            }
        }
    cout << ans <<endl;
    return 0;
}

-1

l上弦月l LV 8 @ 2018-03-03 12:57:22

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
bool map[105][105];
int x[12] = {-2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2};//储存搜索范围 
int y[12] = {0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0};
int n, m, ans = 0;
struct node
{
    int x, y;
};
int main( )
{
    cin >> n >> m;
    char temp;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> temp;
            if (temp == '#')
               map[i][j] = true;
            else 
               map[i][j] = false;
        }
    queue <node> bfsQueue;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (map[i][j])
            {
                node tempNode;
                tempNode.x = i;
                tempNode.y = j;
                bfsQueue.push(tempNode);
                while (!bfsQueue.empty())
                {
                    node t = bfsQueue.front();
                    bfsQueue.pop();
                    for (int k = 0; k < 12; k++)
                        if (map[t.x + x[k]][t.y + y[k]] && (t.x + x[k]) > 0 && (t.x + x[k]) <= n && (t.y + y[k]) > 0 && (t.y + y[k]) <= m)
                        {
                            map[t.x + x[k]][t.y + y[k]] = false;
                            tempNode.x = t.x + x[k];
                            tempNode.y = t.y + y[k];
                            bfsQueue.push(tempNode);
                        }
                }
                ans++;
            }
        }
    cout << ans <<endl;
    return 0;
}

-1

sheng123 LV 7 @ 2018-02-10 20:20:38

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define ll long long
#define MAXN 10000005
using namespace std;

char a[1005][1005];
int n ,m ,ans ;
int color[12][2] = {{1,0},/*{}{}{}{}{}{}{}{}{}{}{}重点！！！！！不是（）（）（）（）（）（）（）（）（）调了30min 55555555*/{1,1},{-1,0},{-1,1},{1,-1},{-1,-1},{0,1},{0,-1},{2,0},{0,2},{-2,0},{0,-2}};
int judge(int x,int y)
{
if(x > 0 && x <= n && y <= m && y > 0)
{
return 1 ;
}
return 0 ;
}

void dfs(int x,int y)
{
for(int i = 0;i < 12;i++)
{
int x1 = x + color[i][0];
int y1 = y + color[i][1];
if(judge(x1,y1) == 1 && a[x1][y1] == 1)
{
a[x1][y1] = 0;
dfs(x1,y1);
}
}
}

int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
scanf("%s",a[i]+1);
for(int j = 1;j <= m;j++)
{
if(a[i][j] == '#')
{
a[i][j] = 1;
}
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(a[i][j] == 1)
{
a[i][j] = 0;
dfs(i,j);
ans++;
}
}
}
cout << ans << endl;
return 0 ;
}

-1

sheng123 LV 7 @ 2018-02-10 19:40:40

#include<cstdio>
#include<cstring>
using namespace std;

int n,m;
char a[120][120];
int lar[12][2] = {{1,0},{1,1},{-1,0},{-1,1},{1,-1},{-1,-1},{0,1},{0,-1},{2,0},{0,2},{-2,0},{0,-2}};

int panduan(int x, int y)
{
if(x > 0 && x <= n && y > 0 && y <= m)
{
return 1;
}

return 0;

}

void dfs(int x , int y)

{
for(int i = 0 ; i < 12;i++)
{
int x1 = x + lar[i][0];
int y1 = y + lar[i][1];
if(panduan(x1,y1) == 1 && a[x1][y1] == 1)
{
a[x1][y1] = 0;
dfs(x1,y1);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1 ; i<= n;i++)
{
scanf("%s", a[i]+1);
for(int j = 1 ; j <= m;j++)
{
/*scanf("%s", a[i][j]);*/
if(a[i][j] == '#')
{
a[i][j] = 1;
}
}
}
int ans = 0;
for(int i =1 ; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == 1)
{
a[i][j] = 0;
dfs(i,j);
ans++ ;
}
}
}
printf("%d", ans);
return 0;
}
/*dfs + floodfill*/

-1

清风breeze LV 8 @ 2017-11-23 13:53:21

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int s=0;
char map[110][110];
int d[2][4]= {{-2,2,0,0},{0,0,-2,2}};
void init() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>map[i][j];
        }
    }
}
void dfs(int r,int c) {
    if(r>n||r<1||c>m||c<1||map[r][c]=='-') {
        return ;
    }
    map[r][c]='-';
    for(int i=-1; i<=1; i++) {
        for(int j=-1; j<=1; j++) {
            int x=r+i,y=c+j;
            dfs(x,y);
        }
    }
    for(int i=0; i<4; i++) {
        int x=r+d[0][i],y=c+d[1][i];
        dfs(x,y);
    }
}
void solve() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(map[i][j]=='#') {
                dfs(i,j);
                s++;
            }
        }
    }
}
int main() {
    memset(map,'-',sizeof(map));
    init();
    solve();
    cout<<s;
    return 0;
}

-1

吴哥——传奇 LV 8 @ 2017-10-04 22:25:12

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>  
#include <cmath>  
#include <cstring>  
#include <set>  
using namespace std;
int a[110][110]={0},n,m;
int c_x[13]={0,0,-1,0,1,-2,-1,1,2,-1,0,1,0},c_y[13]={0,-2,-1,-1,-1,0,0,0,0,1,1,1,2};
bool check(int x,int y)
{
    if(x<=0||y<=0||x>n||y>m||!a[x][y])
        return false;
    return true;
}
void dfs(int x,int y)
{
    for(int i=1;i<=12;i++)
    {
        int n_x=x+c_x[i];
        int n_y=y+c_y[i];
        if(check(n_x,n_y))
            a[n_x][n_y]=0,dfs(n_x,n_y);
    }
} 
int main()  
{
    int num=0,i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        char line[110]={0};
        scanf("%s",line);
        for(j=1;j<=m;j++)
        {
            if(line[j-1]=='#')
                a[i][j]=1;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j])
                a[i][j]=0,dfs(i,j),num++;
        }
    }
    printf("%d\n",num);
    return 0;  
}

-1

一叶一菩提 LV 4 @ 2017-07-05 16:52:44

BFS

#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char map[110][110];
char a;
bool visited[110][110];
int n,m;
void BFS(int i,int j) {
    visited[i][j]=0;
    if(i-1>=1&&visited[i-1][j]) {
        BFS(i-1,j);
    }
    if(i+1<=n&&visited[i+1][j]) {
        BFS(i+1,j);
    }
    if(j-1>=1&&visited[i][j-1]) {
        BFS(i,j-1);
    }
    if(j+1<=m&&visited[i][j+1]) {
        BFS(i,j+1);
    }
    if(i+1<=n&&j+1<=m&&visited[i+1][j+1]) {
        BFS(i+1,j+1);
    }
    if(i-1>=1&&j-1>=1&&visited[i-1][j-1]) {
        BFS(i-1,j-1);
    }
    if(i+1<=n&&j-1>=1&&visited[i+1][j-1]) {
        BFS(i+1,j-1);
    }
    if(i-1>=1&&j+1<=m&&visited[i-1][j+1]) {
        BFS(i-1,j+1);
    }
    if(i-2>=1&&visited[i-2][j]) {
        BFS(i-2,j);
    }
    if(i+2<=n&&visited[i+2][j]) {
        BFS(i+2,j);
    }
    if(j-2>=1&&visited[i][j-2]) {
        BFS(i,j-2);
    }
    if(j+2<=m&&visited[i][j+2]) {
        BFS(i,j+2);
    }
}
int main() {
    int s=0;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            cin>>a;
            if(a=='#') {
                visited[i][j]=1;
            } else visited[i][j]=0;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            if(visited[i][j]) {
                s++;
                BFS(i,j);
            }
        }
    cout<<s<<endl;
    return 0;
}

YLFX @ 2017-07-11 15:08:47

题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题水水水水题题题题题题题题题题题题题题题题题题题题题题题题题题题题题水水水水水水水水水题题题题题题题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题题题题题题题题题题题题题题水水水水题水水水水水水水水水水水题题题题题题题题题题题题题题题题题题水水水水水水水题水水水题题水水水水水题题题题题…
laplaceking @ 2017-11-12 11:27:05

这是DFS啊。。。

-1

larryzhong LV 9 @ 2017-06-01 13:07:54

思路: dfs;
注意点: dfs 后将访问的节点得值改为 '-'.
附: c++ AC 代码:

#include <iostream>
#include <cmath>
using namespace std;

const int maxn = 110;
int n, m, _count;
bool vis[maxn][maxn];
string map[maxn];

void dfs(int i, int j) {
    map[i][j] = '-';
    for (int dx = -2; dx <= 2; dx++) {
        for (int dy = -2; dy <= 2; dy++) {
            if (abs(dx) + abs(dy) <= 2) {
                int x = i + dx, y = j + dy;
                if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == '#') {
                    dfs(x, y);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == '#') {
                dfs(i, j);
                _count++;
            }
        }   
    }
    cout << _count << endl;
    return 0;
}

-1

PowderHan LV 10 @ 2017-05-07 22:21:43

裸bfs
直接上代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <queue>
using namespace std;

struct node
{
    int x,y;
};
int we;
bool map[102][102];
int n,m;
int ans;
queue<node> q;

void bfs(int x,int y)
{
    node p;
    p.x=x,p.y=y;
    q.push(p);
    map[x][y]=0;

    while(!q.empty())
    {
        node r=q.front();
        q.pop();

        for(int i=-2;i<=2;i++)
        {
            for(int j=-2;j<=2;j++)
            {
                if(abs(i)+abs(j)>2)
                    continue;
                int newx=r.x+i;
                int newy=r.y+j;
                if(newx>=1&&newy>=1&&newy<=m&&newx<=n&&map[newx][newy])
                {
                    map[newx][newy]=0;
                    node o;
                    o.x=newx;
                    o.y=newy;
                    q.push(o);
                }
            }   
        }
    }
    ans++;
}

int main()
{
    char ch;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>ch;
            if(ch=='#')
                map[i][j]=1;
            else
                map[i][j]=0;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(map[i][j])
                bfs(i,j);
    cout<<ans<<endl;
    return 0;
}

题解

276 条题解

送给圣诞夜的极光

信息

状态

开发

支持

题解

276 条题解

送给圣诞夜的极光

信息

状态

开发

支持

还没有账户？

登录