绿色电器公司网站psd模板,旅游网站技术方案,南宁建站热搜,在哪个网站找水利工地做题目描述 Description小浣熊松松和朋友到野外露营#xff0c;没想到遇上了pi;年一次的大洪水#xff0c;好在松松是一只爱观察的小浣熊#xff0c;他发现露营地的地形和洪水有如下性质#xff1a; ①露营地可以被看做是一个N*M的矩形方阵#xff0c;其中左上角坐标为… 题目描述 Description 小浣熊松松和朋友到野外露营没想到遇上了pi;年一次的大洪水好在松松是一只爱观察的小浣熊他发现露营地的地形和洪水有如下性质 ①露营地可以被看做是一个N*M的矩形方阵其中左上角坐标为(1,1)右下角坐标为(n,m)每个格子(i,j)都有一个高度h(i,j)。 ②洪水送(r,c)开始如果一个格子被洪水淹没那这个格子四周比它低或相同的格子也会被淹没。 现在松松想请你帮忙算算有多少个格子不会被淹没便于他和朋友逃脱。 【原有误数据已删除】 输入描述 Input Description 第一行包含两个整数nm表示矩形方阵右下角坐标。 以下n行每行m个数第i行第j个数表示格子(i,j)的高度。 最后一行包含两个整数rc表示最初被洪水淹没的格子。 输出描述 Output Description 输出仅一行为永远不会被淹没的格子的数量。 样例输入 Sample Input 3 3 1 2 3 2 3 4 3 4 5 2 2 样例输出 Sample Output 5 数据范围及提示 Data Size Hint 对于90%的数据保证随机生成。 对于100%的数据1N,M1000。 标签是bfs 我只会用dfs。 下面是dfs爆搜。 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
using namespace std;int n,m,h[1002][1002],a,b,ans1;
int xx[5]{-1,1,0,0},yy[5]{0,0,1,-1};
bool w[1002][1002],vis[1002][1002];void dfs(int x,int y)
{vis[x][y]1;for(int i0;i4;i){int dxxxx[i],dyyyy[i];if(dx1||dxn||dy1||dym||w[dx][dy]1||vis[dx][dy]1) continue;if(h[dx][dy]h[x][y]){w[dx][dy]1;ans;}}for(int i1;in;i)for(int j1;jm;j)if(w[i][j]1!vis[i][j]) dfs(i,j);
}int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jm;j)scanf(%d,h[i][j]);scanf(%d%d,a,b);w[a][b]1;dfs(a,b);printf(%d,n*m-ans);
} DFS75 这个也是dfs还是很慢不过能过这道题 对比一下思路吧。 #includecstdio
#includeiostream
using namespace std;int next[4][2] {{0,1},{0,-1},{1,0},{-1,0}};
int mp[1000][1000];
int a[1000][1000];
int n,m,sum0;void dfs(int x,int y)
{sum;int t;tmp[x][y];int i,j;for(i0; i4; i){int xxxnext[i][0];int yyynext[i][1];if(xx1||yy1||xxn||yym)continue ;if(mp[xx][yy]ta[xx][yy]0){a[xx][yy]1;dfs(xx,yy);}}
}int main()
{int i,j;cinnm;for(i1; in; i)for(j1; jm; j)cinmp[i][j];int x;int y;cinxy;a[x][y]1;dfs(x,y);coutn*m-sumendl;return 0;
} dfs AC 有人说这是个bfs的板子。 hh反正我不会。 狗子zxl又在外面发火了。。。 另附一份bfsAC代码。 自行理解。 #includeiostream
#includequeue
using namespace std;struct point
{int x,y;
};int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}};
int lock[1001][1001] {0};
int a[1001][1001];
int n, m, sum0;void BFS(int x, int y)
{queue point q;point now, next;now.x x, now.y y;q.push(now);lock[now.x][now.y] -1;while(!q.empty()){now q.front();for(int i0; i4; i){next.x now.x dir[i][0];next.y now.y dir[i][1];if(next.x0||next.y0||next.xn||next.ym) //判断是否越界continue;if((a[next.x][next.y]a[now.x][now.y])lock[next.x][next.y]!-1)//如果洪水可以淹没且点没有访问过{q.push(next); //该点入栈lock[next.x][next.y] -1;}}q.pop();sum;}
}int main()
{int p1, p2;cinnm;for(int i1; in; i){for(int j1; jm; j)cina[i][j];}cinp1p2;BFS(p1,p2);coutn*m-sumendl;return 0;
} bfs 转载于:https://www.cnblogs.com/Mary-Sue/p/9163418.html
