A40217. 估计人数
填空题
困难
知识点
题目描述
估计人数
题目描述
给定一个 NX M 的方格矩阵，矩阵中每个方格标记 0 或者 1代表这个方格是不是有人踩过。
已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1,包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘
请你计算至少有多少人在矩阵上走过
输入格式
输入第一行包含两个整数 N、M。
以下 N 行每行包含 M 个整数 (0/1)，代表方格矩阵
输出格式
输出一个整数代表答案。
样例输入
5 5
00100
11111
00100
11111
00100
样例输出
3
参考答案
#include<bits/stdc++.h>
using namespace std;
int n , m;
int Match[810] , Visit[810] , Map[810][810];
char String[30][30];
inline int ID(int a , int b , int k) { return (a - 1) * m + b + n * m * k; }
int Dfs(int x)
{
for(int i = 1 ; i <= n * m ; ++i)
{
if(Map[x][i + n * m] && !Visit[i + n * m])
{
Visit[i + n * m] = 1;
if(!Match[i + n * m] || Dfs(Match[i + n * m]))
{
Match[i + n * m] = x;
return 1;
}
}
}
return 0;
}
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; ++i)
cin >> (String[i] + 1);
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
if(String[i][j] == '1')
{
int a , b;
a = i + 1; b = j;
if(a < 1 || b < 1 || a > n || b > m || String[a][b] == '0');
else
Map[ID(i , j , 0)][ID(a , b , 1)] = 1;
a = i; b = j + 1;
if(a < 1 || b < 1 || a > n || b > m || String[a][b] == '0');
else
Map[ID(i , j , 0)][ID(a , b , 1)] = 1;
}
for(int a = 1 ; a <= n ; ++a) for(int b = 1 ; b <= m ; ++b) if(String[a][b] == '1')
for(int c = 1 ; c <= n ; ++c) for(int d = 1 ; d <= m ; ++d) if(String[c][d] == '1')
if(!Map[ID(a , b , 0)][ID(c , d , 1)])
{
for(int s = 1 ; s <= n ; ++s) for(int t = 1 ; t <= m ; ++t)
if(String[s][t] == '1' && Map[ID(a , b , 0)][ID(s , t , 1)] && Map[ID(s , t , 0)][ID(c , d , 1)])
{
Map[ID(a , b , 0)][ID(c , d , 1)] = 1;
goto bk;
}
bk:;
}
// cout << Map[ID(2 , 3 , 0)][ID(1 , 3 , 1)] << '\n';
int Answer = 0;
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j) if(String[i][j] == '1')
{
for(int a = 1 ; a <= n ; ++a)
for(int b = 1 ; b <= m ; ++b)
Visit[ID(a , b , 1)] = 0;
if(!Dfs(ID(i , j , 0))) Answer++;
}
cout << Answer << '\n';
return 0;
}
上一题
下一题