Untitled
unknown
c_cpp
a year ago
1.8 kB
13
Indexable
Never
#include "bits/stdc++.h" // @JASPER'S BOILERPLATE using namespace std; using ll = long long; #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) #define REP(i, b) for(int i = 0; i < b; i++) #define PER(i, b) for(int i = b - 1; i >= 0; i--) #define fi first #define se second #ifdef JASPER2 #include "debug.h" #else #define debug(...) 166 #endif using pii = pair < int, int >; const int INF = 1e9; const int MOD = 1e9 + 7; const int N = 1e2 + 5; int n, m; string s; bool found, used[N][N]; char a[N][N]; int dx[] = {0, 0, -1, 1}; int dy[] = {-1, 1, 0, 0}; void solve(int i, int j, int pos) { // tai o (i, j), tai vi tri pos cua xau S; if (found == true || pos == (int) s.size()) { found = true; return; } for (int k = 0; k < 4; ++k) { int ni = i + dx[k]; int nj = j + dy[k]; if (1 <= ni && ni <= n && 1 <= nj && nj <= m && !used[ni][nj] && a[ni][nj] == s[pos]) { used[ni][nj] = 1; solve(ni, nj, pos + 1); used[ni][nj] = 0; } } } void run_case() { cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j]; cin >> s; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (a[i][j] == s[0]) { used[i][j] = 1; solve(i, j, 1); used[i][j] = 0; } } } cout << (found? "YES\n" : "NO\n"); } signed main() { cin.tie(0) -> sync_with_stdio(0); #ifdef JASPER2 freopen("in1", "r", stdin); #endif int Test = 1; //cin >> Test; for (int test = 1; test <= Test; test++){ run_case(); } }