Submission #59366776

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
#define F first
#define S second

const int N = 13;
int n, m, k;
string mat[N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool check(int i, int j, vector<vector<bool> > &visited){
    if(i < 0 || j < 0 || i >= n || j >= m || visited[i][j] || mat[i][j] == '#'){
        return 0;
    }
    return 1;
}

int dfs(int i, int j, vector<vector<bool> > &visited, int curr){
    if(curr == k){
        return 1;
    }
    int ans = 0;
    for(int a = 0; a < 4; a++){
        int newi = i + dx[a], newj = j + dy[a];
        if(check(newi, newj, visited)){
            visited[newi][newj] = 1;
            ans += dfs(newi, newj, visited, curr + 1);
            visited[newi][newj] = 0;
        }
    }
    return ans;
}


int32_t main(){
    FAST
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){
        cin >> mat[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            vector<vector<bool> > visited(n, vector<bool>(m, 0));
            if(mat[i][j] == '.'){
                visited[i][j] = 1;
                ans += dfs(i, j, visited, 0);
            }
        }
    }
    cout << ans;
    return 0;
}

Submission Info

Judge Result