4*4 matrix, walk from top left to right bottom, and you can go in 4 directions: up, down, left, right. You cannot revisit a location twice. Now, count all unique ways.
4*4 matrix, walk from top left to right bottom, and you can go in 4 directions: up, down, left, right. You cannot revisit a location twice. Now, count all unique ways.
Read full article from 4*4 matrix, walk from top left to right bottom, and you can go in 4 directions: up, down, left, right. You cannot revisit a location twice. Now, count all unique ways.
4*4 matrix, walk from top left to right bottom, and you can go in 4 directions: up, down, left, right. You cannot revisit a location twice. Now, count all unique ways.
| bool is_valid(int i, int j) { return i >= 0 && i < 4 && j >= 0 && j < 4; | |
| } | |
| void dfs(int &ways, int len, int i, int j, vector<vector<bool>>& visited) { | |
| if(len == 4) { | |
| ways++; | |
| return; | |
| } | |
| if(is_valid(i, j) && visited[i][j] == false) { // cannot change the order of these two statement!!!!!!! | |
| visited[i][j] = true; dfs(ways, len+1, i-1, j, visited); visited[i][j] = false; | |
| visited[i][j] = true; dfs(ways, len+1, i+1, j, visited); visited[i][j] = false; | |
| visited[i][j] = true; dfs(ways, len+1, i, j-1, visited); visited[i][j] = false; | |
| visited[i][j] = true; dfs(ways, len+1, i, j+1, visited); visited[i][j] = false; | |
| } | |
| } | |
| int main() { | |
| int ways = 0, len = 0; | |
| vector<vector<bool>> visited(4, vector<bool>(4, false)); | |
| dfs(ways, len, 0, 0, visited); | |
| cout << ways << endl; // my answer is 40 | |
| } |
