各位大佬都是深搜啊。。。
这里补一个广搜的代码
写丑了不要介意

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char map[510][510];
int yan[510][510],dx[300010],dy[300010],bx[5]={0,1,-1,0,0},by[5]={0,0,0,1,-1};
int main()
{
    int nx,ny,x,y,i,k,sum=0,nowx,nowy,head=1,tail=1,c;
    cin>>nx>>ny;
    for(i=1;i<=nx;i++)
      for(k=1;k<=ny;k++)
       cin>>map[i][k];
    for(k=1;k<=nx;k++)
     {
        if(map[k][1]=='0')
        yan[k][1]=1;
        else
        continue;
        tail=1,head=1;
        dx[1]=k,dy[1]=1;    
       while(head>=tail)
      {
        nowx=dx[tail];
        nowy=dy[tail];
        for(i=1;i<=4;i++)
        {
            x=nowx+bx[i];
            y=nowy+by[i];
            if(x>0&&x<=nx&&y>0&&y<=ny&&map[x][y]=='0'&&yan[x][y]==0)
            {
                head++;
                dx[head]=x;
                dy[head]=y;
                yan[x][y]=1;
            }
        }
        tail++;
     }
     }
     for(k=1;k<=nx;k++)
     {
        if(map[k][ny]=='0')
        yan[k][ny]=1;
        else
        continue;
        tail=1,head=1;
        dx[1]=k,dy[1]=ny;   
       while(head>=tail)
      {
        nowx=dx[tail];
        nowy=dy[tail];
        for(i=1;i<=4;i++)
        {
            x=nowx+bx[i];
            y=nowy+by[i];
            if(x>0&&x<=nx&&y>0&&y<=ny&&map[x][y]=='0'&&yan[x][y]==0)
            {
                head++;
                dx[head]=x;
                dy[head]=y;
                yan[x][y]=1;
            }
        }
        tail++;
     }
     }
     for(k=1;k<=ny;k++)
     {
        if(map[1][k]=='0')
        yan[1][k]=1;
        else
        continue;
        tail=1,head=1;
        dx[1]=1,dy[1]=k;    
       while(head>=tail)
      {
        nowx=dx[tail];
        nowy=dy[tail];
        for(i=1;i<=4;i++)
        {
            x=nowx+bx[i];
            y=nowy+by[i];
            if(x>0&&x<=nx&&y>0&&y<=ny&&map[x][y]=='0'&&yan[x][y]==0)
            {
                head++;
                dx[head]=x;
                dy[head]=y;
                yan[x][y]=1;
            }
        }
        tail++;
     }
     }
     for(k=1;k<=ny;k++)
     {
        if(map[nx][k]=='0')
        yan[nx][k]=1;
        else
        continue;
        tail=1,head=1;
        dx[1]=nx,dy[1]=k;   
       while(head>=tail)
      {
        nowx=dx[tail];
        nowy=dy[tail];
        for(i=1;i<=4;i++)
        {
            x=nowx+bx[i];
            y=nowy+by[i];
            if(x>0&&x<=nx&&y>0&&y<=ny&&map[x][y]=='0'&&yan[x][y]==0)
            {
                head++;
                dx[head]=x;
                dy[head]=y;
                yan[x][y]=1;
            }
        }
        tail++;
     }
     }
     for(i=1;i<=nx;i++)
      for(k=1;k<=ny;k++)
       if(map[i][k]=='0'&&yan[i][k]==0)
         sum++;
     cout<<sum;
     return 0;
}

BFS,理解为水从边框的0向里漫，被水淹没的标记为+，最后统计没被淹没的0的个数。

#include <iostream>
#include <queue>

using namespace std;

typedef struct
{
    int x,y;
}point;

int m,n;
char c[500][500];
queue<point> que;
int ans=0;

int main()
{
    cin>>m>>n;
    int i,j;
    point it,pu;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>c[i][j];
        }
    }
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==0||i==m-1||j==0||j==n-1)
            {
                if(c[i][j]=='0')
                {
                    it.x=i;
                    it.y=j;
                    que.push(it);
                    while(!que.empty())
                    {
                        it=que.front();
                        que.pop();
                        c[it.x][it.y]='+';
                        if(it.x>0)
                        {
                            if(c[it.x-1][it.y]=='0')
                            {
                                pu.x=it.x-1;
                                pu.y=it.y;
                                que.push(pu);
                            }
                        }
                        if(it.x<m-1)
                        {
                            if(c[it.x+1][it.y]=='0')
                            {
                                pu.x=it.x+1;
                                pu.y=it.y;
                                que.push(pu);
                            }
                        }
                        if(it.y>0)
                        {
                            if(c[it.x][it.y-1]=='0')
                            {
                                pu.x=it.x;
                                pu.y=it.y-1;
                                que.push(pu);
                            }
                        }
                        if(it.y<n-1)
                        {
                            if(c[it.x][it.y+1]=='0')
                            {
                                pu.x=it.x;
                                pu.y=it.y+1;
                                que.push(pu);
                            }
                        }
                    }
                }
            }
        }
    }
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(c[i][j]=='0')
            {
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

简单的DFS｡◕‿◕｡

#include<iostream>
using namespace std;
int x,y,k=0;
char a[600][600];
void sub(int,int);
void sub(int i,int j)
{
    a[i][j]='s';
    if(a[i-1][j]=='0')
    sub(i-1,j);
    if(a[i+1][j]=='0')
    sub(i+1,j);
    if(a[i][j-1]=='0')
    sub(i,j-1);
    if(a[i][j+1]=='0')
    sub(i,j+1);
}
int main()
{
    cin>>x>>y;
    for(int i=1;i<=x;++i)
    {
        for(int j=1;j<=y;++j)
        {
            cin>>a[i][j];
        }
    } 
    for(int i=1;i<=y;++i)
    if(a[1][i]=='0')
    sub(1,i);
    for(int i=1;i<=y;++i)
    if(a[x][i]=='0')
    sub(x,i);
    for(int i=1;i<=x;++i)
    if(a[i][1]=='0')
    sub(i,1);
    for(int i=1;i<=x;++i)
    if(a[i][y]=='0')
    sub(i,y);
    for(int i=1;i<=x;++i)
    {
        for(int j=1;j<=y;++j)
        {
            if(a[i][j]=='0')
            k++;
        }
    }
    cout<<k;
    return 0;
}

/*
灌水法深搜，注意边界处理。还需要判断是否曾来过，减少不必要搜索。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

int n,m;
char a[502][502];
int zx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int x,int y)
{
if(x>n||x<1||y<1||y>m)
return;
if(a[x][y]==1)//此句应在下一句前
return;
if(a[x][y]=='0')
a[x][y]=1;
if(a[x][y]=='*')
return;
for(int i=0;i<4;i++)
{
int newx=x+zx[i][0];
int newy=y+zx[i][1];
dfs(newx,newy);
}
}

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i]+1;
for(int i=1;i<=n;i++)
{

dfs(i,1);

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

dfs(1,i);

dfs(n,i);
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='0')
ans++;
cout<<ans<<endl;
return 0;
}

so water

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>  
#include <cmath>  
#include <cstring>  
#include <set>  
using namespace std;
int a[510][510]={0},all=0,temp=0,e=1,m,n;
int xku[5]={0,1,-1,0,0},yku[5]={0,0,0,1,-1};
void bfs(int x,int y)
{
    for(int i=1;i<=4;i++)
    {
        int n_x=x+xku[i],n_y=y+yku[i];
        if(n_x>0&&n_y>0&&n_x<=n&&n_y<=m)
        {
            if(!a[n_x][n_y])
            {
                temp+=e;
                a[n_x][n_y]=1;
                bfs(n_x,n_y);
            }
        }
        else
        {
            e=0;
            temp=0;
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char line[510]={0};
        scanf("%s",line);
        for(int j=1;j<=m;j++)
        {
            if(line[j-1]=='*')
                a[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                temp=1;
                e=1;
                a[i][j]=1;
                bfs(i,j);
                all+=temp;
            }   
        }
    }
    printf("%d",all);
    return 0;  
}  #include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>  
#include <cmath>  
#include <cstring>  
#include <set>  
using namespace std;
int a[510][510]={0},all=0,temp=0,e=1,m,n;
int xku[5]={0,1,-1,0,0},yku[5]={0,0,0,1,-1};
void bfs(int x,int y)
{
    for(int i=1;i<=4;i++)
    {
        int n_x=x+xku[i],n_y=y+yku[i];
        if(n_x>0&&n_y>0&&n_x<=n&&n_y<=m)
        {
            if(!a[n_x][n_y])
            {
                temp+=e;
                a[n_x][n_y]=1;
                bfs(n_x,n_y);
            }
        }
        else
        {
            e=0;
            temp=0;
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char line[510]={0};
        scanf("%s",line);
        for(int j=1;j<=m;j++)
        {
            if(line[j-1]=='*')
                a[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                temp=1;
                e=1;
                a[i][j]=1;
                bfs(i,j);
                all+=temp;
            }   
        }
    }
    printf("%d",all);
    return 0;  
}  

DFS 把边界设为水,vis[]标记
#include <cstdio>
#include <cstring>
#define is_ok(i,j) (0<=i&&i<=n+1&&0<=j&&j<=m+1&&vis[i][j]==0&&A[i][j]!='*')

int n,m;
int star=0,count=0;
char A[600][600];

int vis[600][600]={0};

void dfs(int x,int y){
if(A[x][y]=='0')
count++;
vis[x][y]=1;
if(is_ok(x+1,y)) dfs(x+1,y);
if(is_ok(x-1,y)) dfs(x-1,y);
if(is_ok(x,y+1)) dfs(x,y+1);
if(is_ok(x,y-1)) dfs(x,y-1);
}

int main(){
memset(A,'W',sizeof(A));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf(" %c",&A[i][j]);
if(A[i][j]=='*')
star++;
}
dfs(0,0);
printf("%d",m*n-star-count);
return 0;
}

水题
var n,m,i,j,ans:longint;
a:array [0..500,0..500] of char;

procedure find(x,y:longint);
begin
if a[x,y]='0' then
begin
a[x,y]:='*';
find(x-1,y);
find(x,y-1);
find(x,y+1);
find(x+1,y);
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
begin
find(i,1);
find(i,m);
end;
for i:=1 to m do
begin
find(1,i);
find(n,i);
end;
for i:=1 to n do
for j:=1 to m do
if a[i,j]='0' then
inc(ans);
write(ans);
end.

一个方框搜一下全部标记‘*’，看一看剩下数量

P1294拯救OIBH总部
Accepted

记录信息

评测状态 Accepted
题目 P1294 拯救OIBH总部
递交时间 2015-08-10 17:37:13
代码语言 C++
评测机 VijosEx
消耗时间 141 ms
消耗内存 1104 KiB
评测时间 2015-08-10 17:37:14

评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:33:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
cin >> a[i] + 1;
^

测试数据 #0: Accepted, time = 0 ms, mem = 1076 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 1040 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 1052 KiB, score = 10

测试数据 #3: Accepted, time = 31 ms, mem = 1104 KiB, score = 10

测试数据 #4: Accepted, time = 18 ms, mem = 1100 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 1092 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 1060 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 1052 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 1092 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 1064 KiB, score = 10

Accepted, time = 141 ms, mem = 1104 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>

using namespace std;

int n , m;
char a[500 + 5][500 + 5];
bool vis[500 + 5][500 + 5];
int i , j;

void dfs( int x , int y )
{
if( x < 0 || y < 0 || x > n + 1 || y > m + 1 )
return;
if( vis[x][y] )
return;
if( a[x][y] == '*' )
return;
vis[x][y] = 1;
dfs( x - 1 , y );
dfs( x + 1 , y );
dfs( x , y - 1 );
dfs( x , y + 1 );
return;
}

int ans;

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
cin >> a[i] + 1;
for( i = 1 ; i <= n ; i++ )
{
dfs( i , 1 );
dfs( i , m );
}
for( i = 1 ; i <= m ; i++ )
{
dfs( 1 , i );
dfs( n , i );
}
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= m ; j++ )
if( !vis[i][j] && a[i][j] == '0' )
ans++;
cout << ans << endl;
return 0;
}
这坑人的水题

program exam1294;
const dx:array[1..4]of longint=(-1,1,0,0);
dy:array[1..4]of longint=(0,0,-1,1);
var n,m,i,j,tot:longint;
f:array[0..600,0..600]of integer;
h:array[0..20000,0..2]of longint;
s:char;

procedure bfs(p,q:longint);
var i,t,w,x,y:longint;
begin
f[p,q]:=1;
t:=1;
w:=1;
h[1,1]:=p; h[1,2]:=q;
repeat
for i:=1 to 4 do
begin
x:=h[t,1]+dx[i];
y:=h[t,2]+dy[i];
if (x>0)and(x<=n)and(y>0)and(y<=m)and(f[x,y]=0) then
begin
inc(w);
h[w,1]:=x;
h[w,2]:=y;
f[x,y]:=1;
end;
end;
inc(t);
until t>w;
end;

begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(s);
if s='0' then f[i,j]:=0 else f[i,j]:=1;
end;
readln;
end;
tot:=0;
for i:=1 to n do
for j:=1 to m do
if ((i=1)or(j=1)or(i=n)or(j=m))and(f[i,j]=0) then bfs(i,j);
for i:=1 to n do
for j:=1 to m do
if f[i,j]=0 then inc(tot);
writeln(tot);
end.
第一次零分 第二次满分
零分 和 满分的差距让我受不了

有问题吗？？？
const
way:array[1..4,1..2] of integer=((1,0),(0,1),(-1,0),(0,-1));
var
a:array[-1..600,-1..600] of char;
s,d,f,g,k,sum:longint;
procedure try(x,y:longint);
var
h,j,kk:longint;
begin
h:=x; j:=y;
for kk:=1 to 4 do
if a[h+way[kk,1],j+way[kk,2]]='0' then begin
a[h+way[kk,1],j+way[kk,2]]:='*';
try(h+way[kk,1],j+way[kk,2]);
end;
end;
begin
readln(s,d);
for f:=1 to s+1 do begin
a[0,f]:='0';
a[d+1,f]:='0';
end;
for f:=1 to d+1 do begin
a[f,0]:='0';
a[f,s+1]:='0';
end;
for f:=1 to s do begin
for g:=1 to d do read(a[f,g]);
readln;
end;
a[0,0]:='*';
try(0,0);
for f:=1 to s do
for g:=1 to d do
if a[f,g]='0' then inc(sum);
writeln(sum);
end.

pascal用到字符串的一定要用**ansi**string!

floodfill算法

program oibh(input,output);
var a:array[0..501,0..501] of char;
sss:char;
ans,i,j,x,y,k,l,m:longint;
begin
readln(y,x);
for i:=1 to x do
begin
for j:=1 to y do
begin
read(a[i,j]);
end;
readln;
end;
for i:=1 to x do
for j:=1 to y do
begin
if(a[i,j]='0')and(a[i-1,j]='*')and(a[i+1,j]='*')and(a[i,j+1]='*')and(a[i,j-1]='*') then inc(ans);
end;
write(ans);

end.
我的哪里错了，怎么会WA0分？

本人弱菜：请问各位大神我的程序哪里错了，只得了30分，BFS：
const dx:array[1..4] of integer=(1,0,-1,0);
dy:array[1..4] of integer=(0,1,0,-1);
var
i,j,k,m,n:longint;
s:string;
f:array[1..500,1..500] of boolean;
q:array[1..2,1..250000] of integer;
procedure sou(x,y:longint);
var i,xx,yy,t,l:longint;
begin
t:=0;l:=1;q[1,1]:=x;q[2,1]:=y;f[x,y]:=false;inc(k);
while t<=l do
begin
inc(t);
xx:=q[1,t];yy:=q[2,t];
for i:=1 to 4 do
if (xx+dx[i]>0)and(xx+dx[i]<=n)and(yy+dy[i]>0)and(yy+dy[i]<=m)
and(f[xx+dx[i],yy+dy[i]]) then
begin
f[xx+dx[i],yy+dy[i]]:=false;
inc(k);
inc(l);
q[1,l]:=xx+dx[i];
q[2,l]:=yy+dy[i];
end;
end;
end;
begin
fillchar(f,sizeof(f),true);
readln(n,m);
for i:=1 to n do
begin
readln(s);
for j:=1 to m do
if s[j]='*' then begin f[i,j]:=false;inc(k); end;
end;
for i:=1 to n do
begin
if f[i,1] then sou(i,1);
if f[i,m] then sou(i,m);
end;
for i:=1 to m do
begin
if f[1,i] then sou(1,i);
if f[n,i] then sou(n,i);
end;
writeln(n*m-k);
end.

样例似乎错了？

暴搜完成。

编译通过...

├ 测试数据 01：答案正确... (0ms, 1680KB)

├ 测试数据 02：答案正确... (109ms, 1660KB)

├ 测试数据 03：答案正确... (0ms, 1664KB)

├ 测试数据 04：答案正确... (0ms, 1688KB)

├ 测试数据 05：答案正确... (0ms, 1680KB)

├ 测试数据 06：答案正确... (0ms, 1680KB)

├ 测试数据 07：答案正确... (0ms, 1672KB)

├ 测试数据 08：答案正确... (0ms, 1668KB)

├ 测试数据 09：答案正确... (0ms, 1684KB)

├ 测试数据 10：答案正确... (0ms, 1672KB)

…………把m和n反过来读入就过了………………rp不好

floodfill,在地图外再加一圈0,从(0,0)开始搜

呼 我也非搜索

program vijos_p1294;

const

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

max=9;

var

map:array[0..501,0..501] of boolean;

find:array[0..501,0..501] of boolean;

y,x,iy,ix,num:longint;

c:char;

function pd(iy,ix:longint):boolean;

var i,ty,tx:longint;

begin

for i:=1 to 4 do

begin

ty:=d+iy;

tx:=d+ix;

if ((ty>=1) and (ty=1) and (tx

编译通过...

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

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

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

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

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

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

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

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

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

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

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

H2O~

DFS秒杀~

晒晒程序 半梦半醒间 写得很不好看……

Const

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

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

Var

a:array [0..501,0..501] of Char;

f:array [0..501,0..501] of Boolean;

i,j,tot,x,y:Longint;

Procedure try(x1,y1:Longint);

Var

i:Longint;

Begin

f[x1,y1]:=true;

For i:=1 to 4 Do

If (x1+dx[i]=1) Then

If (y1+dy[i]=1) Then

If (f[x1+dx[i],y1+dy[i]]=false) and (a[x1+dx[i],y1+dy[i]]='0') Then

try(x1+dx[i],y1+dy[i]);

End;

Begin

Readln(x,y);

For i:=1 to x Do Begin

For j:=1 to y Do Read(a);

Readln;

End;

For i:=1 to x Do If (a='0') and (f=false) Then try(i,1);

For i:=1 to x Do If (a='0') and (f=false) Then try(i,y);

For i:=1 to y Do If (a[1,i]='0') and (f[1,i]=false) Then try(1,i);

For i:=1 to y Do If (a[x,i]='0') and (f[x,i]=false) Then try(x,i);

tot:=0;

For i:=1 to x Do

For j:=1 to y Do If (f=false) and (a='0') Then Inc(tot);

Writeln(tot);

End.