Problem:1569 新建题解

Solution_ID:33137            dfs

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<cstring>
using namespace std;
const int N=1000;
char arr[N][N];
int brr[N][N];
int n,m,leap=0;
void dfs(int a,int b){
 if(a<0||b<0||a>=n||b>=m)
  return;
 if(arr[a][b]=='.'||brr[a][b])
  return;
 brr[a][b]=leap;
 dfs(a+1,b);
 dfs(a-1,b);
 dfs(a,b+1);
 dfs(a,b-1);
}
int main()
{
 memset(brr,0,sizeof(brr));
 cin>>n>>m;
 for(int i=0;i<n;i++){
  for(int j=0;j<m;j++){
   cin>>arr[i][j];
  }
 }
 for(int i=0;i<n;i++){
  for(int j=0;j<m;j++){
   if(arr[i][j]=='#'&&!brr[i][j]){
    leap++;
    dfs(i,j);
   }
  }
 }
 cout<<leap;
 return 0;
 }


by 89731 八月 29, 2019, 3:54 p.m.

Solution_ID:33005            把这当做简单的判断来做就行了!!

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <iostream>
using namespace std;
int r,c;
char a[101][101];
int ans=0;
int main()
{
 cin>>r>>c;
 for(int i=1;i<=r;i++)
 {
  for(int j=1;j<=c;j++)
  {
   cin>>a[i][j];
   if(a[i][j]=='#'&&a[i+1][j]!='#'&&a[i-1][j]!='#'&&a[i][j+1]!='#'&&a[i][j-1]!='#')
      ans++;
  }
 }
 cout<<ans<<endl;
 return 0;
}


by 92140 八月 4, 2019, 8:59 p.m.

Solution_ID:31317            加一点就能够打印染色后的地图,深

                   时间复杂度:Θ() 空间复杂度:Θ()

/*

作者:浅浅35166

题目:p1569 最佳绿草

*/


/*

//如何写一份可以提交的代码?以P1000 A+B为例

#include <iostream>

using namespace std;

int main()

{

    int a, b; //定义两个变量名

    cin >> a >> b; //从标准输入流中输入两个整数

    cout << a + b << endl; //输出到标准输出流中


}

// 完成程序以后,点击下方的提交,即可看到测试结果

*/

#include<bits/stdc++.h>

using namespace std;

int a[101][101];

int next[4][4]={{0,1},{1,0},{0,-1},{-1,0}};

int m,n;

void dfs(int x,int y,int col){

a[x][y] = col;

int tx,ty;

for(int i=0;i<4;i++){

tx = x+next[i][0];

ty = y+next[i][1];

if(tx<1||ty<1||tx>m||ty>n)

continue;

if(a[tx][ty]>0)

dfs(tx,ty,col);

}

return;

}


int main(){


char c;

cin>>m>>n;

int col=0;

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++){

cin>>c;

if(c=='.')

a[i][j]=0;

else

a[i][j]=1;

}

}

/*for(int i=1;i<=m;i++){     //打印二维数组 

for(int j=1;j<=n;j++){

cout<<a[i][j]<<" ";

}

cout<<endl;

} */

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++){

if(a[i][j]>0){

col--;

dfs(i,j,col);

}

}

}

  • cout<<-col<<endl;

}


by 50747 五月 20, 2018, 5:14 p.m.

Solution_ID:31251            深搜

                   时间复杂度:Θ( ) 空间复杂度:Θ( )

这里写题解#include <cstdio>

#include <iostream>

using namespace std;


int m,n,ma[1000][1000],flg=0;

char mi[1000][1000];


void dfs(int s,int t)

{

if(mi[s][t]!='#'||ma[s][t]==1)

return;

if(s>0&&t>0&&s<=m&&t<=n&&mi[s][t]=='#')

{

ma[s][t]=1;

}

dfs(s+1,t);

dfs(s-1,t);

dfs(s,t+1);

dfs(s,t-1);

}

int main()

{

cin>>m>>n;

for(int i=1;i<=m;i++)

{

for(int j=1;j<=n;j++)

{

cin>>mi[i][j];

}

}

for(int x=1;x<=m;x++)

for(int y=1;y<=n;y++)

{

if(mi[x][y]=='#'&&ma[x][y]!=1)

{

dfs(x,y);

flg+=1;

}

}

cout<<flg;

return 0 ;

}


by 44173 四月 28, 2018, 2:11 p.m.

Solution_ID:28522            20行吧把他当循环做就行了

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream> 

#include<cstring>

using namespace std;

char dt[102][102];

int js=0;

int main()

{

int r,c;

cin>>r>>c;

for(int i=1;i<=r;i++)

 for(int j=1;j<=c;j++)

   cin>>dt[i][j];

for(int i=1;i<=r;i++)

 for(int j=1;j<=c;j++)

 {

if(dt[i][j]=='#')

   {

    js++;

    dt[i+1][j]='.';

    dt[i-1][j]='.';

    dt[i][j-1]='.';

    dt[i][j+1]='.';

}

 } 

cout<<js; 

return 0;

}


by 60937 八月 6, 2017, 7:46 p.m.

Solution_ID:27881            lol

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
using namespace std;
int next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char ma[200][2001];
int r,c,ans=0;
int DFS(int x,int y)
{
    ma[x][y]='.';
    int i,j,xz,yz;
    for(i=0;i<4;i++)
    {
        xz=x+next[i][0];
        yz=y+next[i][1];
        if(xz>=0&&xz<r&&yz>=0&&yz<c)
        {
            if(ma[xz][yz]=='#')
            {
                DFS(xz,yz);
            }
        }
    }
}
int main()
{
    int i,j;
    cin>>r>>c;
    for(i=0;i<r;i++)
        cin>>ma[i];
    for(i=0;i<r;i++)
    {
        for(j=0;j<c;j++)
        {
            if(ma[i][j]=='#')
            {
                DFS(i,j);
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

by 44175 七月 14, 2017, 8:28 a.m.

Solution_ID:27877            haha

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>
#include<iostream>
using namespace std;
int mp[1000][1000];
char a[1000];
int n,num=0;
int next[4][2]={{0,1},{0,-1},{1,0},{0,-1}};
void dfs(int x,int y)
{
    int xx,yy,i;
    mp[x][y]=num;
    for(i=0;i<4;i++)
    {
        xx=x+next[i][1];
        yy=y+next[i][0];
        if(mp[xx][yy]==-1)
            dfs(xx,yy);
    }
}
int main()
{
    int i,j,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%s",a);
        for(j=0;j<m;j++)
        {
            if(a[j]=='#')
                mp[i][j+1]=-1;
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(mp[i][j]==-1)
            {
                num++;
                dfs(i,j);
            }
        }
    cout<<num<<endl;
}

by 41906 七月 13, 2017, 9:54 p.m.

Solution_ID:27112            orz哇哈哈

                   时间复杂度:Θ(o(nm)) 空间复杂度:Θ(o(nm))

#include <cstdio>

#include <iostream>

using namespace std;

int main(){

bool a[110][110]={0};

char aa[110][110];

int n,m,s=0;

cin>>n>>m;

for(int c=1;c<=n;c++)

 for(int cc=1;cc<=m;cc++)

   {cin>>aa[c][cc];if(aa[c][cc]=='#')a[c][cc]=1;}

    for(int c=1;c<=n;c++)

      for(int cc=1;cc<=m;cc++)

        if(a[c][cc]){

        s++;

        a[c][cc]=0;

        a[c+1][cc]=0;

        a[c][cc-1]=0;

        a[c][cc+1]=0;

        a[c+1][cc]=0;

}

printf("%d\n",s);

return 0;

}


by 51792 六月 2, 2017, 4:06 p.m.

Solution_ID:27030            无标题 orz 哇哈哈

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <cstdio>

#include <iostream>

using namespace std;

int main(){

bool a[110][110]={0};

char aa[110][110];

int n,m,s=0;

cin>>n>>m;

for(int c=1;c<=n;c++)

 for(int cc=1;cc<=m;cc++)

   cin>>aa[c][cc];

for(int c=1;c<=n;c++)

 for(int cc=1;cc<=m;cc++)

   if(aa[c][cc]=='#')a[c][cc]=1;

    for(int c=1;c<=n;c++)

      for(int cc=1;cc<=m;cc++)

        if(a[c][cc]){

        s++;

        a[c][cc]=0;

        a[c+1][cc]=0;

        a[c][cc-1]=0;

        a[c][cc+1]=0;

        a[c+1][cc]=0;

}

printf("%d\n",s);

return 0;

}


by 51792 五月 27, 2017, 10:02 a.m.

Solution_ID:26979            水题!直接判断!

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <iostream>
using namespace std;
bool a[200][200]={false};
int i,j,m,n,cnt=0;
char b;//全局变量;
int main()
{   cin>>m>>n;
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            cin>>b;
            if(b=='#'){
                a[i][j]=true;
            }else a[i][j]=false;
        }
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            if(a[i+1][j]||a[i][j+1]){//合并,去重!
                a[i][j]=false;
            }
        }
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            if(a[i][j]){
                cnt++;
            }
        }
    }cout <<cnt<< endl;
    return 0;
}


by 52260 五月 24, 2017, 12:35 p.m.

Solution_ID:26743            预读取大法好

                   时间复杂度:Θ() 空间复杂度:Θ()

program grass;

var ch:char;

    a:array[0..100,0..100] of boolean;

    b:array[0..100,0..100] of longint;

    r,c,i,j,tot:longint;

begin

 readln(r,c);

 tot:=0;

 for i:=1 to r do

  begin

   for j:=1 to c do

    begin

     read(ch);

     if(ch='#') then

      begin

       a[i,j]:=true;

       if(a[i-1,j]=true) or (a[i,j-1]=true) then

        begin

         if(a[i,j-1]=true) then 

          begin

           b[i,j]:=b[i,j-1];

          end

         else if(a[i-1,j]=true) then

          begin

           b[i,j]:=b[i-1,j];

          end;

        end else

         begin

          inc(tot);

          b[i,j]:=tot;

         end;

      end;

    end;

    readln();

  end;

 writeln(tot);

end.


by 35217 五月 11, 2017, 8:56 a.m.

Solution_ID:24242            。。。(补充版)

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

int main(){

int n,m,b,b1,key=0;

char c;

bool a[200][200]={false};

cin>>n>>m;

for(b=0;b<n;b++)

    for(b1=0;b1<m;b1++){

    cin>>c;

    if(c=='#')a[b][b1]=true;

}

for(b=0;b<n;b++)

   for(b1=0;b1<m;b1++)

       if(a[b][b1])

      if(!a[b+1][b1]&&!a[b][b1+1]) 

        key++;

cout<<key<<endl;

return 0; 


by 47523 一月 2, 2017, 11:50 a.m.

Solution_ID:24236            。。。

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

int main(){

int n,m,b,b1,key=0;

char c;

bool a[200][200]={false};

cin>>n>>m;

for(b=0;b<n;b++)

    for(b1=0;b1<m;b1++){

    cin>>c;

    if(c=='#')a[b][b1]=true;//输入赋值,是草丛为真,不是为假(bool) 

    else a[b][b1]=false;

}

for(b=0;b<n;b++)

   for(b1=0;b1<m;b1++)//从第一个推到最后一个 

    if(a[b+1][b1]||a[b][b1+1])//如果下面一个或者右面一个是草丛的话,自己就会被合并(假设是这样的)(反正最后也是求草丛数,假设可以被合并)如果下面或者右边不是草丛,可证明自己是被合并的最后一个,则为这整个草丛的代表性人物,最后统计用到(反正我是这么想的) 

        a[b][b1]=false;

for(b=0;b<n;b++)

   for(b1=0;b1<m;b1++)//从头到尾统计一遍 

       if(a[b][b1])key++;//如果找到一个代表性人物,就草丛++ 

cout<<key<<endl;

return 0; 


by 47523 一月 2, 2017, 9:43 a.m.

Solution_ID:21169             pascal dfs

                   时间复杂度:Θ() 空间复杂度:Θ()

const

  dx:array[1..4]of longint=(1,-1,0,0);

  dy:array[1..4]of longint=(0,0,1,-1);

var

  map:array[0..100,0..100]of longint;

  r,c,i,j,ans:longint;

  st:string;

procedure try(x,y:longint);

var

  i,tx,ty:longint;

begin

  map[x,y]:=0;

  for i:=1 to 4 do

  begin

    tx:=x+dx[i];

    ty:=y+dy[i];

    if map[tx,ty]=1 then try(tx,ty);

  end;

end;

begin

  readln(r,c);

  for i:=1 to r do

  begin

    readln(st);

    for j:=1 to c do

      if st[j]='#' then map[i,j]:=1

                   else map[i,j]:=0;

  end;

  for i:=1 to r do

    for j:=1 to c do

      if map[i,j]=1 then begin inc(ans);try(i,j);end;

  writeln(ans);

end.


by 43719 九月 4, 2016, 7:05 p.m.

Solution_ID:20325            答案

                   时间复杂度:Θ() 空间复杂度:Θ()

var
  r,c,i,j,total:integer;
  ch:char;
  a:array[-1..101,-1..101] of boolean;
procedure try(i,j:longint);
begin
  a[i,j]:=false;
  if (a[i+1,j]=false)and(a[i-1,j]=false)and(a[i,j-1]=false)and(a[i,j+1]=false) then exit
  else
  begin
    if a[i+1,j]=true then try(i+1,j);
    if a[i,j+1]=true then try(i,j+1);
    if a[i-1,j]=true then try(i-1,j);
    if a[i,j-1]=true then try(i,j-1); 
  end;
end;
begin
  readln(r,c);
  total:=0;
  fillchar(a,sizeof(a),false);
  for i:=1 to r do
  begin
    for j:=1 to c do
    begin
     read(ch);
     if ch='#' then a[i,j]:=true ;
    end;
    readln;
  end;
 for i:=1 to r do
  for j:=1 to c do
   if (a[i,j]=true) then begin inc(total);try(i,j);end;
 writeln(total);
end.


by 40350 八月 3, 2016, 7:10 p.m.

Solution_ID:19960            (刘氏题解)偏要广搜

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<stdio.h>
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int qx[100],qy[100];
int ans=0;
int n,m;
int map[100][100]={0};
void bfs(int x,int y)
{
    int tx,ty,i;
    int head=0,tail=1;
    qx[head]=x;
    qy[head]=y;
    while(head<tail)
    {
        for(i=0;i<4;i++)
        {
            tx=qx[head]+dx[i];
            ty=qy[head]+dy[i];
            if(tx>=0&&ty>=0&&tx<n&&ty<m&&map[tx][ty])
            {
                qx[tail]=tx;
                qy[tail++]=ty;
                map[tx][ty]=0;
            }
        }
        head++;
    }
}
int main()
{   
    int i,j;
    char ch;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            ch=getchar();
            while(ch<'!')ch=getchar();
            if(ch=='#')map[i][j]=1;
        }
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        if(map[i][j])
        {
            bfs(i,j);
            ans++;
        }
    printf("%d",ans);
    return 0;
}

枚举图上每一个点,如果是草丛就开始广搜,将四个方向的草丛入队,并标记为零(被我吃了)

实际上这样操作时间复杂度也就O(n^2),因为走过的点都被我吃了



by 31966 七月 23, 2016, 3:53 p.m.

Solution_ID:18860            字数,字数

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

#include<iostream>

#define M 110

using namespace std;

int map[M][M],vis[M][M];

int n,m,flag,ans;

int a[5]={0,0,0,1,-1};

int b[5]={0,1,-1,0,0};

int out(int x,int y)

{

if(x<1||x>n||y<1||y>m)return 1;

if(map[x][y]=='.')return 1;

if(vis[x][y])return 1;

return 0;

}

void dfs(int x,int y)

{

if(flag==1)return;

if(out(x+1,y)&&out(x-1,y)&&out(x,y+1)&&out(x,y-1))

{

flag=1;

return;

}

for(int i=1;i<=4;i++)

{

int xx=x+a[i],yy=y+b[i];

if(!out(xx,yy))

{

vis[xx][yy]=1;

dfs(xx,yy);

}

}

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

char c;

for(int j=1;j<=m;j++)

{

cin>>c;

map[i][j]=(int)c;

}

}

for(int i=1;i<=n;i++)

 for(int j=1;j<=m;j++)

 {

  if(map[i][j]=='#'&&!vis[i][j])

  {

  flag=0;

  vis[i][j]=1;

  dfs(i,j);

  ans++;

}

 }

    printf("%d",ans);

    return 0;

}


by 35543 六月 12, 2016, 9:41 p.m.

Solution_ID:18397            典型深搜,心情不好的时候可以拿来

                   时间复杂度:Θ() 空间复杂度:Θ()

这里写题解#include<bits/stdc++.h>
using namespace std;
const int maxN = 105;
int n,m;
int ans = 0;
bool is_raw(int x,int y)
{
    if(x >= 1 && x <= n && y >= 1 && y <= m) return true;
    return false;
}
char maze[maxN][maxN];
int gra[maxN][maxN];
bool vis[maxN][maxN];//是否访问过
int dir[8] = {-1,0,  0,1,  0,-1, 1,0, };//相邻四个方向
void dfs(int x,int y,int num)
{
    for(int i = 0 ; i < 8; i = i + 2)
    {
        if(is_raw(x + dir[i],y + dir[i+1]) && !vis[x + dir[i]][y + dir[i+1]] &&
        !gra[x + dir[i]][y + dir[i+1]])
        {
            vis[x + dir[i]][y + dir[i+1]] = true;
            dfs(x + dir[i],y + dir[i+1],num);
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(vis,0,sizeof(vis));
    for(int i = 1; i <= n ; i++)
    {
        for(int j = 1; j <= m ; j++)
        {
            cin>>maze[i][j];
            if(maze[i][j] =='#') gra[i][j] = 0 ;//草丛
            else gra[i][j] = 1;
        }
    }
    for(int i = 1; i <= n ; i++)
    {
        for(int j = 1; j <= m ; j++)
        {
            if(!vis[i][j] && gra[i][j] == 0)
            {
                ans++;
                vis[i][j] = 1;
                dfs(i,j,ans);
            }
        }
    }
    cout<<ans<<endl;
}


by 26057 五月 19, 2016, 3:41 p.m.

Solution_ID:14273            PASCAL

                   时间复杂度:Θ() 空间复杂度:Θ()

var r,c,i,j,total:integer;

    ch:char;

    a:array[-1..101,-1..101] of boolean;

 procedure try(i,j:longint);

  begin

   a[i,j]:=false;

   if (a[i+1,j]=false) and (a[i-1,j]=false) and (a[i,j-1]=false) and

   (a[i,j+1]=false) then exit

    else begin

     if a[i+1,j]=true then try(i+1,j);

     if a[i,j+1]=true then try(i,j+1);

     if a[i-1,j]=true then try(i-1,j);

     if a[i,j-1]=true then try(i,j-1);  

   end;

  end;

begin

 readln(r,c);

 total:=0;

 fillchar(a,sizeof(a),false);

 for i:=1 to r do 

  begin

   for j:=1 to c do

    begin

     read(ch);

     if ch='#' then a[i,j]:=true ;

    end;

  readln;

  end;

 for i:=1 to r do 

  for j:=1 to c do

   if (a[i,j]=true) then begin inc(total);try(i,j);end;

 writeln(total);

end.


by 19018 十一月 4, 2015, 4:32 p.m.

Solution_ID:10217            经典深搜

                   时间复杂度:Θ(n) 空间复杂度:Θ(n)

var

        grass:array[0..101,0..101] of boolean;

        m,n,i,j,ge:longint;

        ch:char;

        function panduan(a,b:longint):boolean;

        begin

                if grass[a,b] then exit(true);

                        exit(false);

        end;

        procedure tian(a,b:longint);

        begin

                grass[a,b]:=false;

                if panduan(a-1,b) then tian(a-1,b);

                if panduan(a+1,b) then tian(a+1,b);

                if panduan(a,b-1) then tian(a,b-1);

                if panduan(a,b+1) then tian(a,b+1);

        end;

begin

        readln(m,n);

        fillchar(grass,sizeof(grass),false);

        for i:=1 to m do

        begin

                for j:=1 to n do

                begin

                        read(ch);

                        if ch='#' then grass[i,j]:=true;

                end;

                readln;

        end;

        ge:=0;

        for i:=1 to m do

        begin

                for j:=1 to n do

                begin

                        if panduan(i,j) then

                        begin

                                inc(ge);

                                tian(i,j);

                        end;

                end;

        end;

        writeln(ge);

end.



by 12861 八月 2, 2015, 4:23 p.m.