Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <set>
- #include <map>
- #include <bitset>
- #include <algorithm>
- #include <iomanip>
- #include <cmath>
- #include <unordered_set>
- #include <unordered_map>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <cstring>
- #include <numeric>
- #include <random>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define FOR(i, k, l) for(int i = k; i < l; i++)
- #define DFOR(i, k, l) for(int i = k; i > l; i--)
- #define FA(i, k) for(int i = 0; i < int(k.size()); i++)
- #define DFA(i, k) for(int i = int(k.size()) - 1; i > -1; i--)
- #define ASKS(i) for(cin >> (i); (i)--;)
- #define MAXINT 2147483647
- #define endl '\n'
- #define all(x) x.begin(), x.end()
- #define fi first
- #define se second
- vector<int> gr[200011];
- bool used[200011] = {0};
- bool way = false;
- bool dfs(int v, int r) {
- used[v] = true;
- int cnt = 0;
- bool fl = false;
- FA(i, gr[v]) {
- int to = gr[v][i];
- if(!used[to]) {
- cnt++;
- if(to == r) way = true;
- fl = dfs(to, r);
- }
- }
- if((cnt == 0 && v !=r) || fl) return true;
- else return false;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int m,n;
- cin >> n >> m;
- pair<int, char> field[n][m];
- int c = 0;
- FOR(i, 0, n) {
- FOR(j, 0, m) {
- cin >> field[i][j].second;
- field[i][j].first = c;
- c++;
- }
- }
- // FOR(i, 0, n) {
- // FOR(j, 0, m) cout << field[i][j].fi << " " << field[i][j].second << " ";
- // cout << endl;
- // }
- int st, end;
- FOR(i, 0, n) {
- FOR(j, 0, m) {
- if(field[i][j].second != '#') {
- if(i-1 >= 0 && field[i-1][j].second != '#') gr[field[i][j].first].push_back(field[i-1][j].first);
- if(i+1 < n && field[i+1][j].second != '#') gr[field[i][j].first].push_back(field[i+1][j].first);
- if(j-1 >= 0 && field[i][j-1].second != '#') gr[field[i][j].first].push_back(field[i][j-1].first);
- if(j+1 < m && field[i][j+1].second != '#') gr[field[i][j].first].push_back(field[i][j+1].first);
- }
- if(field[i][j].second == '1') st = field[i][j].first;
- if(field[i][j].second == '2') end = field[i][j].first;
- }
- }
- // FOR(i, 0, 15) {
- // FA(j, gr[i]) cout << i <<" " << gr[i][j] << " ";
- // cout << endl;
- // }
- // cout << st << " " << end;
- if(dfs(st, end)) {
- if (way) {
- cout << "YES\n";
- return 0;
- }
- }
- cout << "NO\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment