This is a graph level traversal problem.
Start with the first char of seed string, go to 8 directions for next char. when you try to go next, you can make a turn and keep direction is vertical with previous
direction, only one turn.
Example, you go up, then next possible directions are up, left and right. If you already make a turn, you can only go up.
Code:
#include <iostream> #include <vector> #include <utility> #include <string> using namespace std; string seed; int M, N; vector<vector<char>> all; void processOne(int x, int y, int d, int next, bool tt, vector<bool>& tList, vector<pair<int, int>>& list1, vector<int>& dir){ if (x >=0 && x < M && y >= 0 && y < N && all[x][y] == seed[next]){ pair<int, int> one = make_pair(x, y); list1.push_back(one); dir.push_back(d); tList.push_back(tt); } } int getThePath(vector<pair<int, int>> mList, vector<int> direction, vector<bool> t, int next){ if(next == seed.size()){ return direction.size(); } if(mList.size() == 0){ return 0; } vector<pair<int, int>> curList; vector<int> curDir; vector<bool> turnList; for(int i = 0; i < mList.size(); i++){ int dir = direction[i]; int curR = mList[i].first; int curC = mList[i].second; bool turn = t[i]; switch(dir){ case 0: //right processOne(curR, curC+1, 0, next, turn, turnList, curList, curDir); //right if(turn){ processOne(curR-1, curC, 2, next, false, turnList, curList, curDir); //up processOne(curR+1, curC, 3, next, false, turnList, curList, curDir); //down } break; case 1: //left processOne(curR, curC-1, 1, next, turn, turnList, curList, curDir); //left if(turn) { processOne(curR-1, curC, 2, next, false, turnList, curList, curDir); //up processOne(curR+1, curC, 3, next, false, turnList, curList, curDir); //down } break; case 2: //up processOne(curR-1, curC, 2, next, turn, turnList, curList, curDir); //up if(turn) { processOne(curR, curC-1, 1, next, false,turnList, curList, curDir); //left processOne(curR, curC+1, 0, next, false,turnList,curList, curDir); //right } break; case 3: //down processOne(curR+1, curC, 3, next, turn, turnList, curList, curDir); //down if(turn) { processOne(curR, curC-1, 1, next, false, turnList, curList, curDir); //left processOne(curR, curC+1, 0, next, false, turnList, curList, curDir); //right } break; case 4: //up-left processOne(curR-1, curC-1, 4, next, turn, turnList, curList, curDir); //up-left if(turn) { processOne(curR-1, curC+1, 5, next, false, turnList, curList, curDir); //up-right processOne(curR+1, curC-1, 6, next, false, turnList, curList, curDir); //down-left } break; case 5: //up-right processOne(curR-1, curC+1, 5, next, turn, turnList, curList, curDir); //up-right if(turn) { processOne(curR-1, curC-1, 4, next, false, turnList, curList, curDir); //up-left processOne(curR+1, curC+1, 7, next, false, turnList, curList, curDir); //down-right } break; case 6: //down-left processOne(curR+1, curC-1, 6, next, turn, turnList, curList, curDir); //down-left if(turn) { processOne(curR+1, curC+1, 7, next, false, turnList, curList, curDir); //down-right processOne(curR-1, curC-1, 4, next, false, turnList, curList, curDir); //up-left } break; case 7: //down-right processOne(curR+1, curC+1, 7, next, turn, turnList, curList, curDir); //down-right if(turn) { processOne(curR+1, curC-1, 6, next, false, turnList, curList, curDir); //down-left processOne(curR-1, curC+1, 5, next, false, turnList, curList, curDir); //up-right } break; case 8: //all processOne(curR-1, curC, 2, next, true, turnList, curList, curDir); //up processOne(curR+1, curC, 3, next, true, turnList, curList, curDir); //down processOne(curR, curC-1, 1, next, true, turnList, curList, curDir); //left processOne(curR, curC+1, 0, next, true, turnList, curList, curDir); //right processOne(curR-1, curC-1, 4, next, true, turnList, curList, curDir); //up-left processOne(curR-1, curC+1, 5, next, true, turnList, curList, curDir); //up-right processOne(curR+1, curC-1, 6, next, true, turnList, curList, curDir); //down-left processOne(curR+1, curC+1, 7, next, true, turnList, curList, curDir); //down-right break; default: break; } } return getThePath(curList, curDir, turnList, next+1); } int main() { vector<pair<int, int>> mList; vector<int> direction; vector<bool> turn; cin >> seed; cin >> M; cin >> N; for(int i = 0; i < M; i++){ vector<char> cur; for(int j = 0; j < N; j++){ char c; cin >> c; cur.push_back(c); if(c == seed[0]){ pair<int, int> one = make_pair(i, j); mList.push_back(one); direction.push_back(8); turn.push_back(true); } } all.push_back(cur); } cout<<getThePath(mList, direction, turn, 1)<<endl; }
Comments