fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. #define inrange(i,j,n,m) (i>=0 && i<n && j>=0 && j<m)?true:false
  5. class Solution {
  6. public:
  7.     bool func(vector<vector<char>>& board, string& word,int a,int b){
  8.         int n=board.size(),m=board[0].size();
  9.         vector<vector<int>> visited(n,vector<int>(m,0));
  10.         stack<pair<int,int>> pos;
  11.         stack<int> curr;
  12.         pos.push({a,b});
  13.         curr.push(0);
  14.         while(!pos.empty()){
  15.             int i=pos.top().first;
  16.             int j=pos.top().second;
  17.             visited[i][j]=1;
  18.             int ind=curr.top();
  19.             pos.pop();
  20.             curr.pop();
  21.             if(ind==(word.size()-1)){
  22.                 return true;
  23.             }
  24.             ++ind;
  25.             if(inrange(i+1,j,n,m) && board[i+1][j]==word[ind] && !visited[i+1][j]){
  26.                 pos.push({i+1,j});
  27.                 curr.push(ind);
  28.             }
  29.             if(inrange(i-1,j,n,m) && board[i-1][j]==word[ind] && !visited[i-1][j]){
  30.                 pos.push({i-1,j});
  31.                 curr.push(ind);
  32.             }
  33.             if(inrange(i,j+1,n,m) && board[i][j+1]==word[ind] && !visited[i][j+1]){
  34.                 pos.push({i,j+1});
  35.                 curr.push(ind);
  36.             }
  37.             if(inrange(i,j-1,n,m) && board[i][j-1]==word[ind] && !visited[i][j-1]){
  38.                 pos.push({i,j-1});
  39.                 curr.push(ind);
  40.             }
  41.         }
  42.         return false;
  43.     }
  44.     bool exist(vector<vector<char>>& board, string word) {
  45.         int n=board.size();
  46.         int m=board[0].size();
  47.         for(int i=0;i<n;i++){
  48.             for(int j=0;j<m;j++){
  49.                 if(board[i][j]==word[0]){
  50.                     bool check=func(board,word,i,j);
  51.                     if(check==true){
  52.                         return true;
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.         return false;
  58.     }
  59. };
  60. int main(){
  61. #ifndef ONLINE_JUDGE
  62. 	freopen("input.txt", "r", stdin);
  63. 	freopen("output.txt", "w", stdout);
  64. #endif
  65.     Solution sol;
  66.     vector<vector<char>> vec{{'A','B','C','E'},
  67.                              {'S','F','C','S'},
  68.                              {'A','D','E','E'}};
  69.     string str="ABCB";
  70.     bool ans=sol.exist(vec,str);
  71.     cout<<ans;
  72. }
  73.  
Success #stdin #stdout 0.01s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/foZ4sv
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!