276 条题解

  • 2
    @ 2020-10-11 17:13:26
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    namespace dts
    {
        const int mx[12]={-2,-1,-1,-1, 0, 0,0,0, 1,1,1,2};
        const int my[12]={ 0,-1, 0, 1,-2,-1,1,2,-1,0,1,0};
        
        int n,m,fa[10000],vis[10000];
        char c[100][100];
        
        int checkc(int x,int y)
        {
            if (0<=x&&x<n&&0<=y&&y<m)
                return c[x][y]=='#';
            else
                return 0;
        }
        
        int number(int x,int y)
        {
            return x*m+y;
        }
        
        int findfa(int x)
        {
            if (fa[x]!=x)
                fa[x]=findfa(fa[x]);
            return fa[x];
        }
        
        void main()
        {
            while (~scanf("%d%d\n",&n,&m))
            {
                for (int i=0;i<n;scanf("\n"),i++)
                    for (int j=0;j<m;j++)
                        scanf("%c",&c[i][j]);
                memset(fa,-1,sizeof(fa));
                for (int i=0;i<n;i++)
                    for (int j=0;j<m;j++)
                        if (checkc(i,j))
                            fa[number(i,j)]=number(i,j);
                for (int i=0;i<n;i++)
                    for (int j=0;j<m;j++)
                        if (checkc(i,j))
                            for (int k=0;k<12;k++)
                                if (checkc(i+mx[k],j+my[k]))
                                    if (findfa(number(i,j))!=findfa(number(i+mx[k],j+my[k])))
                                        fa[findfa(number(i+mx[k],j+my[k]))]=findfa(number(i,j));
                int ans=0;
                memset(vis,0,sizeof(vis));
                for (int i=0;i<=number(n-1,m-1);i++)
                    if (fa[i]!=-1)
                        if (vis[findfa(i)]==0)
                            ans++,vis[findfa(i)]=1;
                printf("%d\n",ans);
            }
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 0
    @ 2020-04-30 17:01:39

    讲解:

    这道题一看,各位读者就知道是DFS求连通图,水~,在此贴出DFS的代码和BFS的代码以及编者自己歪歪出的并查集代码。

    代码实现: DFS:

    #include<iostream>
    using namespace std;
    const int nx[13]={0,1,-1,0,0,2,-2,0,0,1,-1,1,-1};
    const int ny[13]={0,0,0,1,-1,0,0,2,-2,-1,1,1,-1};//方向数组
    char a[1001][1001];
    int n,m,ans;
    void dfs(int x,int y)
    {
    int i;
    if(x<1 || x>n || y<1 || y>m || a[x][y]!='#') return;
    //越界或已走过就return
    a[x][y]='-';//标记已走过
    for(i=1;i<=12;i++) dfs(x+nx[i],y+ny[i]);
    }
    int main()
    {
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j];
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=m;j++)
    {
    if (a[i][j]=='#')
    {
    ans++;
    dfs(i,j);
    }
    }
    }
    cout<<ans;
    }
    BFS:

    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<cmath>
    using namespace std;
    char a[101][101];
    int book[101][101],n,m;
    struct note{int x,y;};
    void bfs(int x,int y)
    {

    int tx,ty,k;
    int next[12][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1},{-2,0},{0,-2},{0,2},{2,0}};
    queue<note>q;
    note z;
    q.push((note){x,y});
    book[x][y]=1;
    while(!q.empty())
    {

    z=q.front();
    for(k=0;k<12;k++)
    {
    tx=z.x+next[k][0];
    ty=z.y+next[k][1];
    if(tx<1||tx>n||ty<1||ty>m) continue;
    if(a[tx][ty]=='#'&&book[tx][ty]==0)
    {

    book[tx][ty]=1;
    q.push((note){tx,ty});
    }
    }
    q.pop();
    }
    return;
    }
    int main()
    {

    int i,j,ans=0;
    scanf("%d%d\n",&n,&m);
    //编者实测,没有\n你会wa(wrong answer)
    for(i=1;i<=n;i++) gets(a[i]+1);//没有你会tle(超时)
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]=='#'&&!book[i][j]) bfs(i,j),ans++;
    cout<<ans;

    }
    并查集:

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int inf=110;
    int a[inf][inf],n,m,ans,i,j,f[(inf+1)*(inf+1)];
    int gets(int x)
    {
    if(f[x]==x) return x;
    return f[x]=gets(f[x]);
    }
    void ff(int x,int y)
    {
    int t1=gets(x),t2=gets(y);
    f[t1]=t2;
    return;
    }
    int main()
    {
    char ch[inf];
    scanf("%d%d",&n,&m);
    for(i=1;i<=(n+1)*(inf+1)+(m+1);i++) f[i]=i;
    for(i=1;i<=n;i++)
    {
    scanf("%s",&ch);
    for(j=1;j<=m;j++)
    {
    if(ch[j-1]=='-') a[i][j]=0;
    else a[i][j]=1;
    }
    }
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=m;j++)
    {
    if(a[i][j]==0) continue;
    if(i-1>=1 && a[i-1][j]!=0) ff((i-1)*inf+j,i*inf+j);
    if(i-2>=1 && a[i-2][j]!=0) ff((i-2)*inf+j,i*inf+j);
    if(i+1<=n && a[i+1][j]!=0) ff((i+1)*inf+j,i*inf+j);
    if(i+2<=m && a[i+2][j]!=0) ff((i+2)*inf+j,i*inf+j);
    if(j-1>=1 && a[i][j-1]!=0) ff(i*inf+(j-1),i*inf+j);
    if(j-2>=1 && a[i][j-2]!=0) ff(i*inf+(j-2),i*inf+j);
    if(j+1<=m && a[i][j+1]!=0) ff(i*inf+(j+1),i*inf+j);
    if(j+2<=m && a[i][j+2]!=0) ff(i*inf+(j+2),i*inf+j);
    if(i-1>=1 && j-1>=1 && a[i-1][j-1]!=0) ff((i-1)*inf+(j-1),i*inf+j);
    if(i-1>=1 && j+1<=m && a[i-1][j+1]!=0) ff((i-1)*inf+(j+1),i*inf+j);
    if(i+1<=n && j-1>=1 && a[i+1][j-1]!=0) ff((i+1)*inf+(j-1),i*inf+j);
    if(i+1<=n && j+1<=m && a[i+1][j+1]!=0) ff((i+1)*inf+(j+1),i*inf+j);
    }
    }
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(f[i*inf+j]==i*inf+j && a[i][j]!=0) ans++;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2020-02-26 20:28:27

    bfs,找联通块,挺基础的一道题

    #include<iostream>
    #include<queue>
    using namespace std;
    
    int n,m,ans;
    char s[105][105];
    bool vis[105][105];
    int dx[] = {-2,-1,0,1,2,1,0,-1,-1,0,1,0};
    int dy[] = {0,1,2,1,0,-1,-2,-1,0,1,0,-1};
    struct Node{
        int x,y;
        Node(int a,int b)
        {
            x = a;
            y = b;
        }
    };
    
    queue<Node> q;
    void bfs(int x,int y)
    {
        q.push(Node(x,y));
        vis[x][y] = 1;
        while(!q.empty())
        {
            Node now = q.front();
            q.pop();
            for(int i = 0;i < 12;i++)
            {
                int xx = dx[i]+now.x;
                int yy = dy[i]+now.y;
                if(!vis[xx][yy]&&xx >= 1&&xx <= n&&yy >= 1&&yy <= m&&s[xx][yy] != '-')
                {
                    vis[xx][yy] = 1;
                    q.push(Node(xx,yy));
                }
            }
        }
    }
    int main(void)
    {
        cin>>n>>m;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                cin>>s[i][j];
            }
        }
        
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                if(s[i][j] == '#'&&!vis[i][j])
                {
                    bfs(i,j);
                    ans++;
                }
            }
        }
        
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2019-09-05 19:28:53

    使用DFS进行深度优先搜索,由*题目定义*确定**访问路径**:

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    const int maxn = 1010;
    char G[maxn][maxn];
    bool vis[maxn][maxn];
    int n, m; //for n(y) rows and m(x) collumns
    int X[12] = { 0, 0, 1, 1, 2, 1, 0, 0, -1, -1, -2, -1 };
    int Y[12] = { 2, 1, 1, 0, 0, -1, -1, -2, -1, 0, 0, 1 };
    
    bool judge(int y, int x)
    {//whether across the boarder
        if (x < 0 || y >= n || x >= m || y < 0) {
            return false;
        }
        if (vis[y][x] == true) {
            return false;
        }
        return true;
    }
    
    void DFS(int y, int x)
    {
        if (!judge(y, x)) {//already visited
            return;
        }
        vis[y][x] = true;
        for (int i = 0; i < 12; i++) {
            if (G[y][x] == '#') {
                DFS(y + Y[i], x + X[i]);
            }
            else {
                break;
            }
        }
    }
    
    int DFS_traverse()
    {
        int block = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (G[i][j] == '#' && judge(i, j)) {//is '#' not '-'
                    block++;
                }
                DFS(i, j);
            }
        }
        return block;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        fill(vis[0], vis[0] + maxn * maxn, false);
        fill(G[0], G[0] + maxn * maxn, '-');
        for (int i = 0; i < n; i++) {
            scanf("%s", &G[i]); //using scanf("%c", G[i][j]); will cause fatal input error
        }
        for (int i = 0; i < n; i++) {//mark: '-' is unreachable boarder
            for (int j = 0; j < m; j++) {
                if (G[i][j] == '-') {
                    vis[i][j] = true;
                }
            }
        }
        int block = 0;
        block = DFS_traverse();
        cout << block;
        return 0; 
    }
    
  • 0
    @ 2019-03-01 20:28:41

    bfs 用了STL的queue和set

    #include<bits/stdc++.h>
    using namespace std;
    queue<pair<int,int>> q;
    set<pair<int,int>> s;
    set<pair<int,int>>::iterator it;
    char c[110][110];
    int v[110][110];
    int d[2][12] = {{1,-1,0,0,2,-2,0,0,1,-1,1,-1},{0,0,1,-1,0,0,2,-2,1,1,-1,-1}};
    int main(){
        int n,m,k=0;
        pair<int,int> cur;
        scanf("%d%d",&n,&m);
        getchar();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%c",&c[i][j]);
                if(c[i][j]=='#') s.insert(make_pair(i,j));
            }
            getchar();
        }
        while(!s.empty()){
            it = s.begin();
            cur = *it; s.erase(cur);
            q.push(cur);
            while(!q.empty()){
                cur = q.front(); q.pop();
                v[cur.first][cur.second] = 1;
                for(int j=0;j<12;j++){
                    int x = cur.first+d[0][j], y = cur.second+d[1][j];
                    if(x<0||y<0||x>=n||y>=m||v[x][y]==1 || c[x][y]!='#') continue;
                    q.push(make_pair(x,y));
                    s.erase(make_pair(x,y));
                    v[x][y] = 1;
                }
            }
            k++;
        }
        printf("%d",k);
    }
    
    
  • 0
    @ 2017-12-22 22:18:45
    
    
    //一个效率极其低下的bfs
    const
        dx:array[1..12] of -2..2 = (-2,-1,-1,-1,0,0,0,0,1,1,1,2);
        dy:array[1..12] of -2..2 = (0,-1,0,1,-2,-1,1,2,-1,0,1,0);
    var
        a:array[-11..111,-11..111] of char;
        i,j,n,m,ans:longint;
        
    procedure bfs(x,y:longint);
    var
        qx,qy:array[1..100001] of longint;
        i,l,r:longint;
        
    function exist(x,y,l,r:longint):boolean;
    var i:longint;
    begin
        for i:=l to r-1 do if (qx[i]=x) and (qy[i]=y) then exit(true);
        exit(false);
    end;
        
    begin
        l:=1; r:=2; qx[l]:=x; qy[l]:=y;
        while l<r do begin
            a[qx[l],qy[l]]:='-';
            for i:=1 to 12 do
                if (a[qx[l]+dx[i],qy[l]+dy[i]]='#') and not exist(qx[l]+dx[i],qy[l]+dy[i],l,r) then begin
                    qx[r]:=qx[l]+dx[i]; qy[r]:=qy[l]+dy[i]; inc(r);
                end;
            inc(l);
        end;
        inc(ans);
    end;
    
    begin
        readln(n,m);
        fillchar(a,sizeof(a),'-');
        for i:=1 to n do begin
            for j:=1 to m do
                read(a[i,j]);
            readln;
        end;
        for i:=1 to n do
            for j:=1 to m do
                if a[i,j]='#' then bfs(i,j);
        writeln(ans);
    end.
    
    
  • 0
    @ 2017-10-25 20:43:23

    水题.⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

    #include<iostream>
    using namespace std;
    char tu[150][150];
    int ans=0;
    int n,m;
    void dfs(int x,int y)
    {
        tu[x][y]='.';
        if(tu[x-2][y]=='#')
        dfs(x-2,y);
        if(tu[x-1][y]=='#')
        dfs(x-1,y);
        if(tu[x-1][y+1]=='#')
        dfs(x-1,y+1);
        if(tu[x][y+1]=='#')
        dfs(x,y+1);
        if(tu[x][y+2]=='#')
        dfs(x,y+2);
        if(tu[x+1][y+1]=='#')
        dfs(x+1,y+1);
        if(tu[x+2][y]=='#')
        dfs(x+2,y);
        if(tu[x+1][y]=='#')
        dfs(x+1,y);
        if(tu[x+1][y-1]=='#')
        dfs(x+1,y-1);
        if(tu[x][y-1]=='#')
        dfs(x,y-1);
        if(tu[x][y-2]=='#')
        dfs(x,y-2);
        if(tu[x-1][y-1]=='#')
        dfs(x-1,y-1);
    }
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=m;++j)
            {
                cin>>tu[i][j];
            }
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=m;++j)
            {
                if(tu[i][j]=='#')
                {
                ans++;
                dfs(i,j);
                }
            }
        }
        cout<<ans;
        return 0;
    }
    
  • 0
    @ 2017-07-05 16:52:41

    这才是完美题解,@YLFX以后别抄我的题解了啊!!!
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    char map[100][100];
    bool visited[100][100];
    int change[2][12]= {{0,-1,0,1,-2,-1,1,2,-1,0,1,0},{-2,-1,-1,-1,0,0,0,0,1,1,1,2}};
    int cc=0;
    int m,n;
    struct point {
    int r,c;
    };
    queue<point> q;
    void BFS(int r,int c) {
    int i,newr,newc;
    bool yes;
    point p;
    point cookie;
    p.r=r;
    p.c=c;
    q.push(p);
    visited[r][c]=1;
    while(!q.empty()) {
    p=q.front();
    q.pop();
    yes=0;
    for(i=0; i<12; i++) {
    newr=p.r+change[0][i];
    newc=p.c+change[1][i];
    if(newc<m&&newc>=0&&newr<n&&newr>=0&&visited[newr][newc]==0&&map[newr][newc]=='#') {
    cookie.r=newr;
    cookie.c=newc;
    q.push(cookie);
    visited[newr][newc]=1;
    }
    }
    }
    cc++;
    }
    int main() {
    memset(map,'-',sizeof(map));
    memset(visited,0,sizeof(visited));
    int i,j;
    cin>>n>>m;
    for(i=0; i<n; i++) {
    for(j=0; j<m; j++)
    cin>>map[i][j];
    }
    for(i=0; i<n; i++) {
    for(j=0; j<m; j++)
    if(visited[i][j]==0&&map[i][j]=='#')
    BFS(i,j);
    }
    cout<<cc;
    return 0;
    }

    • @ 2017-07-05 16:53:32

      唠嗑有包 我要举报你

  • 0
    @ 2017-07-05 16:49:46

    ***上了贼船就应该跟贼走,用了变量就要用到底
    DFS。

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    char map[100][100];
    bool visited[100][100];
    int change[2][12]= {{0,-1,0,1,-2,-1,1,2,-1,0,1,0},{-2,-1,-1,-1,0,0,0,0,1,1,1,2}};
    int cc=0;
    int m,n;
    struct point {
        int r,c;
    };
    queue<point> q;
    void BFS(int r,int c) {
        int i,newr,newc;
        bool yes;
        point p;
        point cookie;
        p.r=r;
        p.c=c;
        q.push(p);
        visited[r][c]=1;
        while(!q.empty()) {
            p=q.front();
            q.pop();
            yes=0;
            for(i=0; i<12; i++) {
                newr=p.r+change[0][i];
                newc=p.c+change[1][i];
                if(newc<m&&newc>=0&&newr<n&&newr>=0&&visited[newr][newc]==0&&map[newr][newc]=='#') {
                    cookie.r=newr;
                    cookie.c=newc;
                    q.push(cookie);
                    visited[newr][newc]=1;
                }
            }
        }
        cc++;
    }
    int main() {
        memset(map,'-',sizeof(map));
        memset(visited,0,sizeof(visited));
        int i,j;
        cin>>n>>m;
        for(i=0; i<n; i++) {
            for(j=0; j<m; j++)
                cin>>map[i][j];
        }
        for(i=0; i<n; i++) {
            for(j=0; j<m; j++)
                if(visited[i][j]==0&&map[i][j]=='#')
                    BFS(i,j);
        }
        cout<<cc;
        return 0;
    }
    

  • 0
    @ 2016-05-18 21:22:31

    bfs
    ~~~
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    using namespace std;
    const int N = 100 + 2;
    char c;
    int m,n,t = 0,A[N][N],used[N][N];
    void read()
    {
    for(int i = 0;i < N;i++)
    for(int j = 0;j < N;j++)
    A[i][j] = used[i][j] = 0;
    scanf("%d%d\n",&n,&m);
    for(int i = 1;i <= n;i++)
    {
    for(int j = 1;j <= m;j++)
    {
    scanf("%c",&c);
    if(c == '#') A[i][j] = 1;
    }
    scanf("\n");
    }
    }
    void search(int x,int y)
    {
    if(!A[x][y] || used[x][y]) return;
    used[x][y] = 1;
    if(x > 1)search(x - 2,y);
    search(x - 1,y - 1);
    search(x - 1,y);
    search(x - 1,y + 1);
    if(y > 1)search(x,y - 2);
    search(x,y - 1);
    search(x,y + 1);
    if(y < m)search(x,y + 2);
    search(x + 1,y - 1);
    search(x + 1,y);
    search(x + 1,y + 1);
    if(x < n)search(x + 2,y);
    }
    void bfs()
    {
    for(int i = 1;i <= n;i++)
    for(int j = 1;j <= m;j++)
    {
    if(A[i][j] && !used[i][j])
    {
    t++;
    search(i,j);
    }
    }
    }
    int main()
    {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    read();
    /*for(int i = 1;i <= n;i++)
    {
    for(int j =1;j <= m;j++)
    printf("%d",A[i][j]);
    printf("\n");
    }*/
    bfs();
    printf("%d\n",t);
    return 0;
    }
    ~~~

  • 0
    @ 2015-11-14 13:30:28

    广度优先搜索
    ```c++
    #include <iostream>
    #include <list>
    #include <queue>

    using namespace std;

    struct Point {
    Point() : x(0), y(0) {}
    Point(int _x, int _y) : x(_x), y(_y) {}

    int x;
    int y;
    }; // struct Point

    typedef list<Point> ListType;
    typedef queue<Point, ListType> Queue;

    #define DEBUG false

    #define NMAX 100
    #define UNLIGHT '-'
    #define LIGHTED '#'

    static int marked[NMAX][NMAX];
    static bool map[NMAX][NMAX];
    static int n, m;

    int Search();
    void _PrintMap();
    void _PrintMarked();

    inline bool Check(const int x, const int y) {
    return marked[x][y] == 0 and map[x][y];
    }

    inline bool Check(const Point &p) { return Check(p.x, p.y); }

    inline bool CheckPlacable(const int x, const int y) {
    return 0 <= x and x < n and 0 <= y and y < m and Check(x, y);
    }

    inline bool CheckPlacable(const Point &p) { return CheckPlacable(p.x, p.y); };

    int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int x = 0; x < n; x++) {
    for (int y = 0; y < m; y++) {
    char c;
    cin >> c;

    if (c == UNLIGHT) { map[x][y] = false; } else {
    map[x][y] = true;
    }

    marked[x][y] = 0;
    } // for
    } // for

    cout << Search();

    if (DEBUG) {
    _PrintMap();
    cout << endl;
    _PrintMarked();
    }

    return 0;
    } // function main

    int Search() {
    #define STATUS_SIZE 12

    const int dx[STATUS_SIZE] = { -2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2 };
    const int dy[STATUS_SIZE] = { 0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0 };

    Queue q;
    int id = 1;

    for (int x = 0; x < n; x++) {
    for (int y = 0; y < m; y++) {
    if (Check(x, y)) {
    q.push(Point(x, y));

    while (!q.empty()) {
    Point p = q.front();
    q.pop();

    if (Check(p)) {
    marked[p.x][p.y] = id;

    for (int i = 0; i < STATUS_SIZE; i++) {
    if (CheckPlacable(p.x + dx[i], p.y + dy[i])) {
    q.push(Point(p.x + dx[i], p.y + dy[i]));
    }
    } // for
    }

    } // while

    id++;
    }
    } // for
    } // for

    return id - 1;

    #undef STATUS_SIZE
    }

    void _PrintMap() {
    for (int x = 0; x < n; x++) {
    for (int y = 0; y < m; y++) { cout << map[x][y]; } // for

    cout << endl;
    } // for
    }

    void _PrintMarked() {
    for (int x = 0; x < n; x++) {
    for (int y = 0; y < m; y++) { cout << marked[x][y] << " "; } // for

    cout << endl;
    } // for
    }

  • 0
    @ 2015-09-05 22:38:44

    ###简单的广搜

    记录信息
    评测状态 Accepted
    题目 P1051 送给圣诞夜的极光
    递交时间 2015-09-05 22:38:06
    代码语言 C++
    评测机 VijosEx
    消耗时间 54 ms
    消耗内存 1316 KiB
    评测时间 2015-09-05 22:38:07
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 612 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 608 KiB, score = 10
    测试数据 #3: Accepted, time = 3 ms, mem = 632 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 636 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #8: Accepted, time = 36 ms, mem = 636 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 1316 KiB, score = 10
    Accepted, time = 54 ms, mem = 1316 KiB, score = 100
    代码
    #include <iostream>
    #include <stdio.h>
    #include <cmath>
    using namespace std;
    char map[110][110];
    bool been[110][110];
    int n,m,ans;
    void search(int x,int y)
    {
    for(int i=-2;i<=2;i++)
    {
    for(int j=-2;j<=2;j++)
    {
    if(abs(i)+abs(j)>2) continue;
    if(x+i>=0&&x+i<n)
    if(y+j>=0&&y+j<m)
    if(map[x+i][y+j]=='#'&&!been[i+x][j+y])
    {
    been[i+x][y+j]=1;
    search(i+x,y+j);
    }
    }
    }
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",map[i]);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
    if(map[i][j]=='#'&&!been[i][j])
    {
    been[i][j]=1;
    ans++;
    search(i,j);
    }
    }
    printf("%d",ans);
    }

  • 0
    @ 2015-07-07 22:11:05

    FLOODFILL轻松过
    代码如下:
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;

    char light[105][105];
    bool visited[105][105];
    int M,N;
    int Fx[]={1,-1,2,-2,0,0,0,0,1,1,-1,-1};
    int Fy[]={0,0,0,0,1,-1,2,-2,1,-1,1,-1};

    void init(){
    cin>>N>>M;
    int i,j;
    for(i=0;i<N;i++)
    for(j=0;j<M;j++)
    cin>>light[i][j];
    return;
    }

    void floodfill(int x,int y){
    visited[x][y]=true;
    int i,dx,dy;
    for(i=0;i<12;i++){
    dx=x+Fx[i];
    dy=y+Fy[i];
    if(dx>=0&&dx<N&&dy>=0&&dy<M&&!visited[dx][dy]&&light[dx][dy]=='#')
    floodfill(dx,dy);
    }
    return;
    }

    void memset(){
    int i,j;
    for(i=0;i<100;i++)
    for(j=0;j<100;j++)
    visited[i][j]=false;
    return;
    }

    int main(){
    init();
    int i,j,ans=0;
    memset();
    for(i=0;i<N;i++)
    for(j=0;j<M;j++)
    if(light[i][j]=='#'&&!visited[i][j]){
    floodfill(i,j);
    ans++;
    }
    cout<<ans;
    return 0;
    }

  • 0
    @ 2015-05-08 17:39:51

    暴力深搜
    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #define LL long long
    #define for1(v,a,b) for (int v=a;v<=b;v++)
    #define for2(v,a,b) for (int v=a;v>=b;v--)
    using namespace std;
    int map[101][101];
    int n,m,ans;
    void Init(){
    char ch;
    scanf("%d%d",&n,&m);
    scanf("%c",&ch);
    for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    scanf("%c",&ch);
    if (ch=='#') map[i][j]=0;
    else map[i][j]=-1;
    }
    scanf("%c",&ch);
    }
    }
    bool Permit(int x,int y){
    if ((x<=0)||(x>n)||(y<=0)||(y>m)) return false;
    if (map[x][y]!=0) return false;
    return true;
    }
    void Dfs(int x,int y){
    map[x][y]=ans;
    if (Permit(x+1,y)) Dfs(x+1,y);
    if (Permit(x+2,y)) Dfs(x+2,y);
    if (Permit(x-1,y)) Dfs(x-1,y);
    if (Permit(x-2,y)) Dfs(x-2,y);
    if (Permit(x,y+1)) Dfs(x,y+1);
    if (Permit(x,y+2)) Dfs(x,y+2);
    if (Permit(x,y-1)) Dfs(x,y-1);
    if (Permit(x,y-2)) Dfs(x,y-2);
    if (Permit(x+1,y+1)) Dfs(x+1,y+1);
    if (Permit(x-1,y+1)) Dfs(x-1,y+1);
    if (Permit(x+1,y-1)) Dfs(x+1,y-1);
    if (Permit(x-1,y-1)) Dfs(x-1,y-1);
    }
    int main(){
    //freopen("p1.in","r",stdin);
    Init();
    ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if (map[i][j]==0){
    ans++;
    Dfs(i,j);
    }
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2015-03-18 22:07:34

    广搜为什么错了

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>

    #include<cstdlib>

    #include<queue>

    #include<cmath>
    using namespace std;
    int n,m,ans,b[12][2]={{1,0},{2,0},{-1,0},{-2,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1},{0,2},{0,-2}};
    char a[240][240];
    bool v[240][240];
    struct node
    {
    int x,y;
    }first;
    void bfs()
    {
    for(int i=0;i<m;i++)
    {
    for(int j=0;j<n;j++)
    {
    if(a[i][j]=='#'&&v[i][j]==0)
    {
    first.x=i;
    first.y=j;
    ans++;

    queue<node> q;
    q.push(first);
    v[first.x][first.y]=1;
    while(!q.empty())
    {
    node now,next;
    now=q.front();
    q.pop();
    for(int i=0;i<12;i++)
    {
    next.x=now.x+b[i][0];
    next.y=now.y+b[i][1];
    if(0<=next.x&&next.x<m&&0<=next.y&&next.y<n&&a[next.x][next.y]=='#'&&v[next.x][next.y]==0)
    {
    v[next.x][next.y]=1;
    q.push(next);
    }
    }
    }
    }
    }
    }
    return ;
    }
    int main()
    {
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
    cin>>a[i];
    }
    memset(v,0,sizeof(v));

    bfs();
    cout<<ans;
    return 0;
    }

  • 0
    @ 2015-02-09 20:44:16

    以每个没有访问的点为源点开始访问,总共的访问次数就是答案。

    Pascal Code

    const
        dx:array[1..12] of longint=(0,1,1,1,0,-1,-1,-1,0,2,0,-2);
        dy:array[1..12] of longint=(1,0,1,-1,-1,-1,1,0,2,0,-2,0);
    var
        b:longint;
        v:array[1..100,1..100] of boolean;    //v数组存储是否访问过
        m,n,i,j:longint;
        c:char;
    procedure visit(x,y:longint);
    var i:longint;
    begin
        if v[x,y] then exit;
        v[x,y]:=true;
        for i:=1 to 12 do
        begin
            if x+dx[i]<1 then continue;    //判断是否超范围
            if x+dx[i]>n then continue;
            if y+dy[i]<1 then continue;
            if y+dy[i]>m then continue;
            visit(x+dx[i],y+dy[i]);
        end;
    end;
    begin
        readln(n,m);
        fillchar(v,sizeof(v),0);
        for i:=1 to n do
        begin
            for j:=1 to m do
            begin
                read(c);
                if c='-' then v[i,j]:=true;    //如果不发光则视为已访问过
            end;
            readln;
        end;
        b:=0;
        for i:=1 to n do
            for j:=1 to m do
                if not v[i,j]
                then begin
                             visit(i,j);
                             inc(b);
                         end;
        writeln(b);
    end.
    
    • @ 2015-02-25 17:12:27

      挺厉害的 很简单的方法啊!!!!!!!

  • 0
    @ 2015-02-04 06:52:44

    #include<iostream>
    #include<string.h>
    #include<stdio.h>
    #include<math.h>
    using namespace std;
    bool a[105][105];
    int xsize, ysize;
    int ans = 0;
    int ab(int n){
    if (n < 0)return -n;
    else return n;
    }
    void visit(int x, int y){
    if (x < 0 || y < 0)return;
    if (x >= xsize || y>ysize)return;
    if (a[x][y] == false)return;
    a[x][y] = false;
    visit(x - 2, y);
    int i, j;
    for (i = -2; i <= 2; i++){
    for (j = -(ab(2 - ab(i))); j <= ab(2 - ab(i)); j++){
    visit(x + i, y + j);
    }
    }
    }
    void go(){
    int i, j;
    for (i = 0; i < xsize; i++){
    for (j = 0; j < ysize; j++){
    if (a[i][j]){
    ans++;
    visit(i, j);
    }
    }
    }
    }
    int main(){
    freopen("in.txt", "r", stdin);
    cin >> xsize >> ysize;
    int i, j;
    char c;
    memset(a, 0, sizeof(a));
    for (i = 0; i < xsize;i++)
    for (j = 0; j < ysize; j++){
    cin >> c;
    if (c == '#')a[i][j] = true;
    }
    go();
    cout << ans << endl;
    return 0;
    }

  • 0
    @ 2014-11-04 16:11:13

    当作Bfs的小练习吧..
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int s[10];
    int dx[]={0,0,0,1,-1,0,0,2,-2,1,1,-1,-1};
    int dy[]={0,1,-1,0,0,2,-2,0,0,-1,1,1,-1};
    const int maxn=1000000+10;
    struct node {
    int x,y;
    }team[maxn];
    bool hash[110][110];
    int bj[110][110];
    char map[110][110];
    int ans=0,n,m;
    void Bfs(int s,int t)
    {
    memset(hash,0,sizeof(hash));
    ans++;
    int head=0,tail=1;
    team[tail].x=s;
    team[tail].y=t;
    hash[s][t]=1;
    bj[s][t]=ans;
    while(head!=tail)
    {
    head++;
    for(int i=1;i<=12;i++)
    {
    int px=team[head].x+dx[i];
    int py=team[head].y+dy[i];
    if(px<=n && px>=1 && py>=1 && py<=m && !hash[px][py] &&!bj[px][py] && map[px][py]!='-')
    {
    tail++;
    team[tail].x=px;
    team[tail].y=py;
    bj[px][py]=bj[team[head].x][team[head].y];
    }
    }
    }
    }
    int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%s",&map[i][1]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(map[i][j]=='#' && !bj[i][j])
    Bfs(i,j);
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2014-10-15 15:11:58

    var
    m,n,i,j,num,a,b:integer;
    tu:array[1..100,1..100]of integer;
    ax:array[1..12]of integer=(-2,-1,-1,-1,0,0,0,0,1,1,1,2);
    ay:array[1..12]of integer=(0,-1,0,1,-2,-1,1,2,-1,0,1,0);
    procedure readin;
    var
    i,j:integer;
    k:char;
    begin
    readln(n,m);
    for i:=1 to n do
    begin
    for j:=1 to m do
    begin
    read(k);
    if k='-' then tu[i,j]:=0
    else tu[i,j]:=1;
    end;
    readln;
    end;
    end;

    procedure work(x,y:integer);
    var
    i,j:integer;
    begin
    tu[x,y]:=0;
    for i:=1 to 12 do
    if (x+ax[i]<=n)and(x+ax[i]>=1)and(y+ay[i]<=m)and(y+ay[i]>=1) then
    if tu[x+ax[i],y+ay[i]]=1 then
    work(x+ax[i],y+ay[i]);
    end;
    begin
    readin;
    num:=0;
    for i:=1 to n do
    for j:=1 to m do
    if tu[i,j]=1 then
    begin
    work(i,j);
    num:=num+1;
    end;
    write(num);
    end.

  • 0
    @ 2014-08-15 18:46:23

    program p1051;
    var
    a:array[-1..102,-1..102]of char;
    n,m,i,j,ans:longint;
    procedure dfs(c,d:longint);
    begin
    if a[c,d]='#' then begin
    a[c,d]:='-';
    dfs(c+1,d);dfs(c+2,d);
    dfs(c-1,d);dfs(c-2,d);
    dfs(c,d+1);dfs(c,d+2);
    dfs(c,d-1);dfs(c,d-2);
    dfs(c+1,d+1);dfs(c-1,d+1);
    dfs(c-1,d-1);dfs(c+1,d-1);end;
    end;
    begin
    readln(n,m);
    for i:=1 to n do begin for j:=1 to m do read(a[i,j]);readln;end;
    for i:=1 to n do for j:=1 to m do
    if a[i,j]='#' then begin dfs(i,j);inc(ans);end;
    writeln(ans);
    end.

信息

ID
1051
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
6211
已通过
2439
通过率
39%
被复制
14
上传者