POJ -3050 Hopscotch

http://poj.org/problem?id=3050

给定一个5×5矩阵，问选6个数的不同排列总数是多少！

二维的搜索，注意要判重，数据量很小，直接用map就好。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<string>
 4 #include<iostream>
 5 #include<map>
 6 using namespace std;
 7 
 8 map<string,int>m;
 9 int f[7][7],ans;
10 int dir[4][2]={-1,0,1,0,0,1,0,-1};
11 
12 void dfs(int x,int y,int num,string s)
13 {
14     if(num==6)
15     {
16         if(m[s]==0)
17         {
18             //cout<<s<<endl;
19             m[s]++;
20             ans++;
21         }
22         return;
23     }
24     for(int i=0;i<4;i++)
25     {
26         int xx=x+dir[i][0];
27         int yy=y+dir[i][1];
28         if(xx>=0&&xx<5&&yy>=0&&yy<5)
29         {
30             string str = s;
31             s+=f[xx][yy]+'0';
32             dfs(xx,yy,num+1,s);
33             s=str;   //这里需要回溯 
34         }
35     }
36 }
37 int main()
38 {
39     //freopen("a.txt","r",stdin);
40     for(int i=0;i<5;i++)
41         for(int j=0;j<5;j++) scanf("%d",&f[i][j]);
42     ans=0;
43     for(int i=0;i<5;i++)
44         for(int j=0;j<5;j++) dfs(i,j,0,"");
45     printf("%d
",ans);
46     return 0;
47 }

View Code