1359：围成面积

大家好，欢迎来到IT知识分享网。

【算法分析】

 解法1：遍历外圈      

       遍历整个地图的外圈（第1行、第1列、第10行，第10列），从外圈所有标记为0的位置开始搜索，把搜索到的位置标记为2。此时所有值为2的位置都是图形外面的位置，值为1的位置是图形的边线，值为0的位置为图形内。统计值为0的位置是数量，即为该图形的面积。

该题用广搜和深搜课可以解题。

解法1广搜代码

#include<bits/stdc++.h> using namespace std; #define N 15 struct Node { int x, y; Node(){} Node(int a, int b):x(a), y(b){} }; int n, a[N][N], ans;//a[i][j]:(i,j)位置标记的数字 int dir[4][2] = { 
  {0, 1}, {0, -1}, {1, 0}, {-1, 0}}; void bfs(int sx, int sy) { queue<Node> que; a[sx][sy] = 2; que.push(Node(sx, sy)); while(que.empty() == false) { Node u = que.front(); que.pop(); for(int i = 0; i < 4; ++i) { int x = u.x + dir[i][0], y = u.y + dir[i][1]; if(x >= 1 && x <= n && y >= 1 && y <= n && a[x][y] == 0) { a[x][y] = 2; que.push(Node(x, y)); } } } } int main() { n = 10;//地图范围：行列1~n for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) cin >> a[i][j]; for(int i = 1; i <= n; ++i)//遍历外圈 { if(a[1][i] == 0) bfs(1, i); if(a[n][i] == 0) bfs(n, i); if(a[i][1] == 0) bfs(i, 1); if(a[i][n] == 0) bfs(i, n); } for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { if(a[i][j] == 0) ans++;//面积加1 } cout << ans; return 0; } 

解法2广搜代码

#include<bits/stdc++.h> using namespace std; #define N 15 struct Node { int x, y; Node(){} Node(int a, int b):x(a), y(b){} }; int n, a[N][N], ans;//a[i][j]:(i,j)位置标记的数字 int dir[4][2] = { 
  {0, 1}, {0, -1}, {1, 0}, {-1, 0}}; void bfs(int sx, int sy) { queue<Node> que; a[sx][sy] = 2; que.push(Node(sx, sy)); while(que.empty() == false) { Node u = que.front(); que.pop(); for(int i = 0; i < 4; ++i) { int x = u.x + dir[i][0], y = u.y + dir[i][1]; if(x >= 0 && x <= n+1 && y >= 0 && y <= n+1 && a[x][y] == 0)//地图范围为0~n+1 { a[x][y] = 2; que.push(Node(x, y)); } } } } int main() { n = 10;//扩展边界后，地图范围：行列 0~n+1 for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) cin >> a[i][j]; bfs(0, 0); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { if(a[i][j] == 0) ans++;//面积加1 } cout << ans; return 0; }