1710: 【基础】跳房子(1768)
内存限制：16 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
格子游戏开始啦。
在一个 的方格矩阵中，每个格子上有一个数字，同学们可以从任何一个格子开始，沿着上下左右四个方向跳跃到相邻的格子。当然啦，在结束游戏之前，同学们不能跳出矩阵，允许同学们跳到自己曾经跳过的格子。
小 同学按上述规则，从任意一个格子出发，跳跃 次，将经过的每个格子的数字连在一起，得到一个 位的数字串（注意：得到的数字串允许以数字 开头，比如：、）。
请问：小 同学最多能得到多少种不同的数字串？
输入
输入共 行，每行 个 位的整数，整数之间用空格隔开。
输出
输出能够组合出的不同数字串的数量。 样例输入 复制
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1样例输出 复制
15提示
【样例解释】
样例中，能得到的不同的数字串有：
, , , , , , , , , , , , , , 。
#include<bits/stdc++.h>
using namespace std;
char a[6][6]={'#'},n=5,ans=0;
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
set<string> ss;
void dfs(string s,int k,int x,int y) {
if (k==6&&s.size()==6) {
ss.insert(s);
return;
}
for (int i=0;i<4;i++) {
if (a[x+dx[i]][y+dy[i]]>='0'&&a[x+dx[i]][y+dy[i]]<='9') {
dfs(s+a[x+dx[i]][y+dy[i]],k+1,x+dx[i],y+dy[i]);
}
}
}
int main(){
int c;
for (int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
cin>>c;
a[i][j]=(char)(c+'0');
}
}
for (int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
string t;
t+=a[i][j];
dfs(t,1,i,j);
}
}
/*
set<string>::iterator it;
for(it=ss.begin();it!=ss.end();it++) {
cout<<*it<<endl;
}
*/
cout<<ss.size();
return 0;
}