P1767 【家族_NOI导刊2010普及(10)】

看到5.7提交 1.4AC我一开始不免有点慌
然而仔细一看确实显然的联通块问题,所以暴力dfs就行了(这道不值得绿吧QAQ

(这些本地跑不停的代码最好在 洛谷在线IDE跑或者用freopen)跑一下)(

#include <cstdio> 
#include <iostream>

using namespace std;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0}; 
int n, ans, len[1005], a[105][205], cnt, vis[105][205];

char ch;

void dfs(int x, int y){
    vis[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int nx = dx[i] + x, ny = dy[i] + y;
        if(nx >= 1 && ny >= 1 && nx <= n && ny <= len[nx] && !vis[nx][ny] && a[nx][ny] != 32 && a[nx][ny] != 42 && a[nx][ny] != 13)//广搜基操
            dfs(nx, ny);
    }
}

int main(){
    scanf("%d",&n);
    getchar();
    while(scanf("%c",&ch) != EOF){//判停
        if(ch == '\n'){
            cnt++;
            continue;
        }
        else {
            len[cnt]++;//每一行长度
            a[cnt][len[cnt]] = ch;//用int存ASCII码
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= len[i]; j++){
            if(!vis[i][j] && a[i][j] != 32 && a[i][j] != 42 && a[i][j] != 13){//ASCII码对照:32 " ";42 "*";13 "\n"(回车
                dfs(i, j);
                ans++;
            }
        }
    }
    printf("%d",ans);
} 

祝大家NOIP RP++ ★,°:.☆( ̄▽ ̄)/$:.°★ 。

上一篇:NOIP 2010 P1514 引水入城


下一篇:每日算法 - day 36