给你一张n*m的西湖地图二值图,其中西湖的轮廓用1表示,轮廓内核轮廓外均用0表示。
现在请你统计西湖的面积,即轮廓内0的个数。
输入包含多组数据,每组数据第一行包含两个正整数n(3≤n≤10)和m(3≤m≤10)。
紧接着有n行,每行m个数字,代表地图,数字之间无空格。
数据保证只有一片连续的湖泊。
对应每一组数据,输出西湖的面积。
10 10 0000000000 0001101000 0010010100 0010000010 0100000010 0100000100 0010001000 0010001000 0011010000 0000100000
26
对于地图的四条边遍历所有的水并填1,最后计数剩下的0的数量。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
#define INF 1000000
using namespace std;
void travel(vector<vector<char>>& map, int x, int y)
{
int m = map.size(), n = map[0].size();
map[x][y] = '1';
if (x > 0 && map[x - 1][y] == '0') travel(map, x - 1, y);
if (x < m - 1 && map[x + 1][y] == '0') travel(map, x + 1, y);
if (y > 0 && map[x][y - 1] == '0') travel(map, x, y - 1);
if (y < n - 1 && map[x][y + 1] == '0') travel(map, x, y + 1);
}
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
int m, n;
while (cin >> m >> n)
{
vector<vector<char>> map(m, vector<char>(n));
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
cin >> map[i][j];
getchar();
}
for (int i = 0; i < m; ++i)
{
if (map[i][0] == '0') travel(map, i, 0);
if (map[i][n - 1] == '0') travel(map, i, n - 1);
}
for (int j = 0; j < n; ++j)
{
if (map[0][j] == '0') travel(map, 0, j);
if (map[m - 1][j] == '0') travel(map, m - 1, j);
}
int res = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (map[i][j] == '0') ++res;
cout << res << endl;
}
return 0;
}
__author__ = 'Yaicky' while True: try: n, m = map(int, raw_input().strip().split()) lake = [] for i in range(n): lake.append(map(int,list(raw_input().strip()))) outarea = 0 topflag, downflag = False, False top, down = 0, n-1 while top!=down: while downflag == False: if sum(lake[down]) == 0: outarea += m down -= 1 elif sum(lake[down]) > 0: downflag = True outarea += m # elif sum(lake[down]) > 1: # downflag = True # down += 1 left, right = 0, m-1 leftflag, rightflag = False, False if sum(lake[top])==0: outarea += m elif sum(lake[top])>0 and topflag==False: outarea += m topflag = True elif sum(lake[top])>0 and topflag==True: while rightflag == False: if lake[top][right] != 1: right -= 1 else: rightflag = True outarea +=1 while left!=right : if lake[top][left] == 0 and leftflag == False: outarea += 1 elif lake[top][left] == 1 and leftflag == False: outarea += 1 leftflag = True elif lake[top][left] == 1 and leftflag == True: outarea += 1 left += 1 top += 1 print m*n - outarea except: break 笨方法。。。。 1.从下往上 找到第一行总和非0的行, 外部面积一直+m 并置flag 2.然后从上往下 找到第一行总和非0的行,外部面积一直+m 并置flag 3.找到上下边界之后,其中的每一行 都先找到右边界,置flag 再从左边找边界 置flag, 左右边界找到了,找中间剩下的1的数量 这些都加在外部面积上 4.直到top遇到down, 总面积-外部面积就好
#include<iostream> #include<string> #include<vector> using namespace std; int main() { int n, m; while (cin >> n >> m) { vector<string> data; int cnt = 0; for (int i = 0; i < n; i++) { string s; cin >> s; data.push_back(s); } for (int i = 0; i < n; i++) { int j = 0; for (; j < m; j++) if (data[i][j] == '1') break; else data[i][j] = '2'; for (j = m-1; j >= 0 ; j--) if (data[i][j] == '1') break; else data[i][j] = '2'; } for (int i = 0; i < m; i++) { int j = 0; for (; j < n; j++) if (data[j][i] == '1') break; else data[j][i] = '2'; for (j = n - 1; j >= 0; j--) if (data[j][i] == '1') break; else data[j][i] = '2'; for (j = 0; j < n; j++) if (data[j][i] == '0') cnt++; } cout << cnt << endl; } return 0; }
#include <iostream> #include <string> #include <queue> #include <vector> using namespace std; struct pos { int x, y; }; int bfs(vector<string> & map, vector<vector<bool> > & visit) { const int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; int n = map.size(), m = map[0].size(); queue<pos> que; pos start{ 0,0 }; que.push(start); visit[start.x][start.y] = true; while (!que.empty()) { pos cur = que.front(), next; que.pop(); for (int i = 0; i < 4; ++i) { next.x = cur.x + dir[i][0]; next.y = cur.y + dir[i][1]; if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && \ !visit[next.x][next.y] && map[next.x][next.y] != '1') { que.push(next); visit[next.x][next.y] = true; } } } int count = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (visit[i][j]) ++count; int one = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (map[i][j] == '1') ++one; return m * n - count - one; } int main() { int n, m; while (cin >> n >> m) { vector<string> mp(n + 2); vector<vector<bool> > visit(n + 2, vector<bool>(m + 2, false)); mp[0] = string(m + 2, '0'); for (int i = 1; i <= n; ++i) { cin >> mp[i]; mp[i] = "0" + mp[i] + "0"; } mp[n+1] = string(m + 2, '0'); cout << bfs(mp, visit) << endl; } return 0; }