【题解】跳房子-C++

Description
奶牛按不太传统的方式玩起小朋友玩的跳房子游戏，现给出一个5*%的由数字组成的网格。它们在格子中向前前跳,向后跳，向左跳，向右跳，跳到网格中另一个数字后，又这样继续跳(可能跳到某个已跳过的数字)。一共在网格中跳过五次后，它们经过的格子数组成一个六位数(可能是0开始头的，例如000201).现问所有可以被跳出来的不同整数的总数。
Input
输入共五行，每行五个数字.
Output
如题
Sample Input
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
Sample Output
15
HINT
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112,

121211, 121212, 211111, 211121, 212111, and 212121 can be constructed.

No other values are possible.

今天考试2题…
又是一道DFS，分别从每个点出发，往四周拓展，不打标记，深度超限就判断当前情况是否出现过，没出现过就标记然后cnt++，查找工作可以交给set来完成，这样就不需要打标记这些了…
ov.

 /*

 这道题看题目描述感觉ans用int存，前导0存不下，所以干脆就用字符串一位一位加

 */

 #include<bits/stdc++.h>

 using namespace std;

 int cnt;

 string ans;

 char mp[][];

 int dir[][]={{,},{-,},{,},{,-}};

 bool in(int x,int y)

 {

     return <=x&&x<=&&<=y&&y<=;

 }

 set<string> s;

 void dfs(int x,int y,int dep,string an)

 {

     an+=mp[x][y];

     if(dep==)

     {

         if(!s.count(an))

         {

             s.insert(an);

             cnt++;

         }

         return;

     }

     for(int i=;i<;i++)

     {

         int nx=x+dir[i][],ny=y+dir[i][];

         if(in(nx,ny))

         {

             dfs(nx,ny,dep+,an);

         }

     }

     return;

 }

 int main()

 {

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)

             cin>>mp[i][j];

     for(int i=;i<=;i++)

     {

         for(int j=;j<=;j++)

         {

             dfs(i,j,,"");

         }

     }

     cout<<cnt<<endl;

     return ;

 }

巴特西

【题解】跳房子-C++

最新文章

热门文章