sundeepblue
4/26/2014 - 3:35 AM

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.

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.

count_ways.cpp
content_copyfile_download
#include <iostream>
#include <vector>
using namespace std;

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
}