炫意html5
最早CSS3和HTML5移动技术网站之一

【洛谷】P1506 拯救oibh总部

题目背景

oibh总部突然被水淹没了!现在需要你的救援……
题目描述

oibh被突来的洪水淹没了>.<还好oibh总部有在某些重要的地方起一些围墙,用*号表示,而一个封闭的*号区域洪水是进不去的……现在给出oibh的围墙建设图,问oibh总部没被淹到的重要区域(由”0″表示)有多少。
输入格式

第一行是两个数,x和y(x,y<=500)

第二行及以下是一个由*和0组成的x*y的图。
输出格式

输出没被水淹没的oibh总部的“0”的数量。
输入输出样例

输入 #1
样例输入1
4 5
00000
00*00
0*0*0
00*00

样例输入2
5 5
*****
*0*0*
**0**
*0*0*
*****

输出 #1
样例输出1
1

样例输出2
5

 

#include<iostream>
using namespace std;
const int MAXN = 500 + 10;
int n, m, ans;
int map[MAXN][MAXN];
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, -1, 1};
void search(int x, int y)
{
map[x][y] = 1;                    //被淹没了 ,标为 1 
for(int i = 1; i <= 4; i++)        //往四个方向搜 

{
int nx = x + dx[i];
int ny = x + dy[i];
if(map[nx][ny] == 0 && nx > 0 && nx <= n && ny > 0 && ny <= m)
{
search(nx, ny);
}
}
}
int main()
{
char e;
cin >> n >> m;
for(int i = 1; i <= n; i++)                //输入 

{
for(int j = 1; j <= m; j++)
{
cin >> e;
if(e == '*')                    //如果是墙,标为 1 

{
map[i][j] = 1;
}
else
{
map[i][j] = 0;                //其他标为 0 

}
}
}
for(int i = 1; i <= n; i++)                //因为谁是从外部淹没,所以从最外层开始搜索 

{
if(map[i][1] == 0)                    //搜索第一列 

{
search(i, 1);
}
if(map[i][m] == 0)                    //搜索最后一列 

{
search(i, m);
}
}
for(int i = 1; i <= m; i++)
{
if(map[1][i] == 0)                    //搜索第一行 

{
search(1, i);
}
if(map[n][i] == 0)                    //搜索最后一行 

{
search(n, i);
}
}
for(int i = 1; i <= n; i++)                //因为被淹没的都与最外层的 0 相连 

{                                        //所以没有被淹没的都被墙堵住了 
for(int j = 1; j <= m; j++)            //搜索剩余的 0 

{
if(map[i][j] == 0)
{
ans++;
}
}
}
/*    for(int i = 1; i <= n; i++)                //测试哪些被淹没
{
for(int j = 1; j <= m; j++)
{
cout << map[i][j];
}
cout << endl;
}
*/
cout << ans << endl;
return 0;
} 

不知道哪里错了,在测试的过程中,样例一 一直过不了。

使用上面测试代码测试后,样例一第二层的 0 还在,应该是递归的某个地方出了问题,可是检查怎么也不知道是哪里错了

救救我!!!

回答

递归中的

int ny = x + dy[i];

改为:

int ny = y + dy[i];

炫意HTML5 » 【洛谷】P1506 拯救oibh总部

Java基础教程Android基础教程