本文主要是介绍CF Bayan 2015 Contest Warm Up B.（dfs+暴力），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Imagine a city with n horizontal streets crossing m vertical streets, forming an (n - 1) × (m - 1) grid. In order to increase the traffic flow, mayor of the city has decided to make each street one way. This means in each horizontal street, the traffic moves only from west to east or only from east to west. Also, traffic moves only from north to south or only from south to north in each vertical street. It is possible to enter a horizontal street from a vertical street, or vice versa, at their intersection.
The mayor has received some street direction patterns. Your task is to check whether it is possible to reach any junction from any other junction in the proposed street direction pattern.
The first line of input contains two integers n and m, (2 ≤ n, m ≤ 20), denoting the number of horizontal streets and the number of vertical streets.
The second line contains a string of length n, made of characters '<' and '>', denoting direction of each horizontal street. If the i-th character is equal to '<', the street is directed from east to west otherwise, the street is directed from west to east. Streets are listed in order from north to south.
The third line contains a string of length m, made of characters '^' and 'v', denoting direction of each vertical street. If the i-th character is equal to '^', the street is directed from south to north, otherwise the street is directed from north to south. Streets are listed in order from west to east.
If the given pattern meets the mayor's criteria, print a single line containing "YES", otherwise print a single line containing "NO".
3 3 ><> v^v
NO
4 6 <><> v^v^v^
YES
The figure above shows street directions in the second sample test case.
解题思路：
题意是说给定n行m列，然后输入两行字符串，> 、< 、v 、^ 分别代表右、左、下、上四个方向，问构成的图是否能保证每个点到另外所有点都连通，能的话输出YES，否则输出NO。
对每一个点进行暴力dfs，判断是否能到其他各点。
完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
string a , b;int n , m;
int vis[1111][1111];
int cnt;
void dfs(int x , int y)
{if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y])return ;vis[x][y] = 1;cnt++;if(a[x] == '>')dfs(x , y + 1);else if(a[x] == '<')dfs(x , y - 1);if(b[y] == '^')dfs(x - 1 , y);else if(b[y] == 'v')dfs(x + 1 , y);
}bool check()
{for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < m ; j++){memset(vis , 0 , sizeof(vis));cnt = 0;dfs(i , j);if(cnt != m * n)return false;}}return true;
}int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endifwhile(~scanf("%d%d",&n,&m)){cin >> a >> b;if(check())printf("YES\n");elseprintf("NO\n");}
}这篇关于CF Bayan 2015 Contest Warm Up B.（dfs+暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
