CodeForces 173B Chamber of Secrets 二分图+最短路
2024-10-18 20:25:49
题目链接:
http://codeforces.com/problemset/problem/173/B
题意:
给你一个n*m的地图,现在有一束激光从左上角往左边射出,每遇到‘#’,你可以选择光线往四个方向射出,或者什么都不做,问最少需要多少个‘#’往四个方向射出才能使关系在n行往右边射出。
题解:
以行和列建二分图,如果str[i][j]=='#',则从i节点到j节点建一条双向边,权值都为1。然后对二分图跑一遍最短路。
代码:
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std; const int maxn = ; vector<int> G[maxn];
char str[maxn][maxn];
int n, m; int inq[maxn], d[maxn];
int spfa() {
queue<int> Q;
memset(inq, , sizeof(inq));
memset(d, 0x7f, sizeof(d)); int ma = d[];
d[] = ; inq[] = ; Q.push();
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int i = ; i < G[u].size(); i++) {
int v = G[u][i];
if (d[v] > d[u] + ) {
d[v] = d[u] + ;
if (!inq[v]) inq[v]=,Q.push(v);
}
}
}
if (d[n] >= ma) return -;
return d[n];
} void init() {
for (int i = ; i <= n + m + ; i++) G[i].clear();
} int main() {
while (scanf("%d%d", &n, &m) == && n) {
init();
for (int i = ; i <= n; i++) scanf("%s", str[i] + );
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
if (str[i][j] == '#') {
G[i].push_back(j + n);
G[j + n].push_back(i);
}
}
}
int ans = spfa();
printf("%d\n", ans);
}
return ;
}
最新文章
- oracle11g的standby性能分析报告statpack安装
- windows命令行下简单使用javac、java、javap详细演示
- [转]What you need to know about transimpedance amplifiers – part 1
- IIS7下,flush无效,解决方案
- Sophos UTM WebAdmin存在未明漏洞
- 西安Uber优步司机奖励政策(2月1日~2月7日)
- SystemTimeToFileTime、FileTimeToLocalFileTime、LocalFileTimeToFileTime三函数的跨平台实现
- java基金会成立
- hdu 3345 War Chess
- C#语言基础——语句
- Aspose.Words for .NET
- C#的一些获取时间的例子
- C++ 常见面试题目
- MySQL 笔记整理(4) --深入浅出索引(上)
- IdentityServer4 中文文档 -10- (快速入门)使用密码保护API
- bzoj2989&;&;4170数列——二进制分组+主席树
- 关于ie6出现的问题的原因归结
- Go Revel - Validation(验证)
- js方法传入对象;js方法传入方法;js方法回调 callback
- spring 在web容器启动时执行初始化方法