本文主要是介绍CodeForces 475B Strongly Connected City[想法],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:http://codeforces.com/problemset/problem/475/B
题目的意思是,给你n条水平固定流向,和m条竖直固定流向的街道,他们互相交叉在一起。。问任意交叉点能不能互相到达。。如下图:
在这里,我们知道,每条路的流向都是已知的。。
那么我们只需要判断外环路能否成环就可以了。。
如果外环路可以成环,那么的话,任意两点就可以到达。否则的话,就不能够。
为什么这么说呢??
因为如果外环路成环了,那么,任意点就可以先走到外环路上,然后,再走到你想要的其他的节点上。。这一点是一定可以的。。
那么怎么判断外环路成环呢?判断四角可达即可。。
Code:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
#define INT unsigned long longint main()
{int n, m;cin >> n >> m;string h, v;cin >> h >> v;bool flag = true;if(h[0] == '>' && v[0] == 'v') flag = false;if(h[0] == '<' && v[m - 1] == 'v') flag = false;if(h[n - 1] == '>' && v[0] == '^') flag = false;if(h[n - 1] == '<' && v[m - 1] == '^') flag = false;
// if(v[0] == v[m - 1]) flag = false;if(flag) puts("YES");else puts("NO");return 0;
}
一个好的想法是非常的重要的!!
这篇关于CodeForces 475B Strongly Connected City[想法]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!