题目描述
暴力
不同路径数
https://www.acwing.com/problem/content/3505/
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
int n,m,k;
unordered_set<int> se;//插入o(1)
int map[7][7];
int dis[4][2]={0,1,0,-1,1,0,-1,0};
int now;
bool isok(int x,int y){
if(x >= 1 && x<=n && y>=1 && y<=m)return true;
return false;
}
void dfs(int x,int y,int pos){
if(pos > k){
se.insert(now);
return ;
}
now = map[x][y] + now*10;
for(int i = 0;i<4;i++){
if(isok(x+dis[i][0],y+dis[i][1]))
dfs(x+dis[i][0],y+dis[i][1],pos+1);
}
now /= 10;
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &map[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
dfs(i,j,0);
printf("%d",se.size());
return 0;
}