（深度优先搜索）POJ 1979的这道题错在哪儿啊验证的结果都是对的，但是总不能ac！

（深度优先搜索）POJ 1979的这道题错在哪里啊？验证的结果都是对的，但是总不能ac！！！
http://poj.org/problem?id=1979

#include <iostream>
using namespace std;

const int MAX_W = 20, MAX_H = 20; 

int W, H, count = 0;
char a[MAX_W][MAX_H];
int ax[] ={1,0,-1,0}, ay[] = {0,-1,0,1};

int dfs (int x, int y)
{
a[x][y] =  '#';
count++;

for (int i = 0; i < 4; i++)
{
int nx = x + ax[i], ny = y + ay[i];
if (0 <= nx && nx <= W && 0 <= ny && ny <= H && a[nx][ny] == '.')
    dfs (nx, ny);
}
return count;
}

int main ()
{
cin >> W >> H;
if ((W <= 0 && H <= 0 )|| (W > MAX_W && H > MAX_H))
    return 0;
for (int i = 0; i < W; i++)
    for (int j = 0; j < H; j++)
        cin >> a[i][j];

for (int i = 0; i < W; i++)
    for (int j= 0; j < H; j++)
        if (a[i][j] == '@')
            dfs (i, j);

cout << count << endl;

return 0;
}

POJ DFS
[解决办法]

设f(x,y)为从点(x,y)出发能够走过的黑瓷砖总数，则：
f(x,y)=1+f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)
需注意的是：凡是走过的瓷砖不能够被重复走过，可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖
#include<iostream>
#include<cstdlib>
using namespace std;
int w,h;
char z[21][21];;
 
 
int f(int x,int y)
{
if(x<0
[解决办法]
x>=w
[解决办法]
y<0
[解决办法]
y>=h)                                                  //如果走出矩阵范围
   return 0;
if(z[x][y]=='#')                                                          //该块瓷砖已被走过
   return 0;
else
{
   z[x][y]='#';                                                    //将走过的瓷砖做标记
   return 1+f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1);
}
}

int main() 
{
int i,j,num;
while(scanf("%d %d",&h,&w),w!=0&&h!=0)
{
   num=0;
   for(i=0;i<w;i++)
    scanf("%s",z[i]);
   for(i=0;i<w;i++)
    for(j=0;j<h;j++)
     if(z[i][j]=='@')
      printf("%d\n",f(i,j));
}
system("pause");
return 0;
}

[解决办法]
哦你这多组数据写得比较奇特，我以为你只处理了一组数据。
你的代码问题是这个
0 <= nx && nx <= H && 0 <= ny && ny <= W
nx==H, ny==W越界。
[解决办法]
“多一少一”问题占程序员常犯错误的10%以上！

将<,<=弄混或将>,>=弄混就是一种典型的“多一少一”问题。

查看更多 下一篇