HENAU 冬令营 搜索专题

J - 二叉树先序遍历

输入一个整数n（n <= 100000），表示二叉树中节点个数，编号为1~n。约定1号节点为二叉树的根节点。然后输入n行，每行包括两个整数，第i行表示编号为i的节点的左子节点和右子节点的编号。如果某个节点没有左子节点，那么对应输行的第一个整数为0；如果某个节点没有右子节点，那么对应行的第二个整数为0。
先序遍历输出此二叉树每个节点的编号，每行输出一个编号。

先序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、前序遍历、前序周游，可记做根左右。前序遍历首先访问根节点然后遍历左子树，最后遍历右子树。

Input

第一行：一个整数n 接下来n行，每行有两个整数

Output

输出n行，每行一个整数，表示节点编号。

Sample Input

5
2 5
3 4
0 0
0 0
0 0

Sample Output

1
2
3
4
5

Select Code

#include
int n;
struct p
{int x;int y;
}p[100005];
void dfs(int x)
{if(x==0)return;printf("%d\n",x);dfs(p[x].x);dfs(p[x].y);}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&p[i].x,&p[i].y);}dfs(1);} 

 K - 迷宫（一）

一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。

输入格式

第一行输入两个整数 nn 和 mm，表示这是一个 n \times mn×m 的迷宫。

接下来的输入一个 nn 行 mm 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。

输出格式

输出一个字符串，如果蒜头君可以逃出迷宫输出"yes"，否则输出"no"。

数据范围

1 \le n, m \le 101≤n,m≤10。

Sample Input

3 4
S**.
..*.
***T

Sample Output

no

Sample Input 2

3 4
S**.
....
***T

Sample Output 2

yes

#include
using namespace std;
int n,m;
int sx,sy,fx,fy;
int xx[4]={-1,1,0,0};
int yy[4]={0,0,1,-1};
int vis[15][15];
int f;
char s[15][15];
void dfs(int x,int y)
{
    for(int i=0;i<=3;i++)
    {
        int dx=x+xx[i];
        int dy=y+yy[i];
        if(dx==fx&&dy==fy)
        {
            f=1;
            return ;
        }
        if(1<=dx&&dx<=n&&1<=dy&&dy<=m&&vis[dx][dy]==0&&vis[dx][dy]!='*')
        {
            vis[dx][dy]=1;
            dfs(dx,dy);
            vis[dx][dy]=0;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            if(s[i][j]=='S')
            sx=i,sy=j;
            if(s[i][j]=='T')
            fx=i,fy=j;
        }
    }
    f=0;
    dfs(sx,sy);
    if(f==1)
    cout<<"yes";
    else
    cout<<"no";
    
    
}
L - 马走日

马在中国象棋以日字形规则移动。请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

Input

第一行为整数T(T < 10)，表示测试数据组数。每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 6, n < 6)

Output

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

Sample Input

1
5 4 0 0

Sample Output

32

#include
#include
int n,m,x,y;
int d=0;
int temp[30][30];
int vis[8][2]={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
void dfs(int x,int y,int tep)
{
    for(int i=0;i<=7;i++)
    {
        int xx=x+vis[i][0];
        int xy=y+vis[i][1];
        if((!temp[xx][xy])&&xx>=0&&xx=0&&xy         {if(tep==n*m)
           {
              d++;
             return ;
           }
           else
            temp[xx][xy]=1;
            dfs(xx,xy,tep+1);
            temp[xx][xy]=0;
            
        }
    }
    
    
}
int main()
{
    int t;
    scanf("%d",&t);
  while(t--)
  {
       memset(temp,0,sizeof(temp));
      d=0;
      scanf("%d %d %d %d",&n,&m,&x,&y);
      temp[x][y]=1;
      dfs(x,y,2);
      printf("%d\n",d);
      
  }
  
   return 0;
 } 

M - 八皇后问题

努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1-991−99 的数字。他又准备了 88 个皇后棋子。

88 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 88 个皇后所在的位置的数字的和是最大的。

输入格式

输入一个数字 k(k\leq 20)k(k≤20)，代表棋盘的数量。

接下来有 kk 个棋盘，每个棋盘有 6464 个数字，分成 88 行 88 列出入，具体可见样例，每一个数字均小于 100100。

输出格式

每一个棋盘对应输出最大的数值， 一共输出 kk 行。

Sample Input

11  2  3  4  5  6  7  89 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Sample Output

260

Select Code

#include
#include
int vis[3][17];
int max;
int tmp[10];
int m[100][100];
void dfs(int i)
{if(i>8){int sum=0;for(int j=1;j<=8;j++)sum=sum+m[j][tmp[j]];if(max

4 3
3 7 12 19

1

#include
#include
int a[100];
int n,k,ans;
int sum;
int prime(int x){for(int i=2;i<=sqrt(x);i++){if(x%i==0)return 0;}return 1;
}
void dfs(int t,int sum,int d){if(t==k){if(prime(sum))ans++;}else{for(int i=d;i

3 5
\\/\\
\\///
/\\\\

1

#include 
#define P pair
#define ff first
#define ss second
using namespace std;
int n,m;
int d[510][510];
char s[510][510];
const int dx[4]={-1,1,1,-1},dy[4]={1,1,-1,-1},val[4]={'/','\\','/','\\'};
const int bias_x[4]={-1,0,0,-1},bias_y[4]={0,0,-1,-1};
deque
 q;
int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) {scanf("%s",s[i]+1);}for(int i=1;i<=n+1;i++)for(int j=1;j<=m+1;j++)d[i][j]=-1;d[1][1]=0; q.push_back(make_pair(1,1));while(q.size()) {P now=q.front(); q.pop_front();if(now.ff==n+1&&now.ss==m+1) break;for(int i=0;i<4;i++) {int nx=now.ff+dx[i],ny=now.ss+dy[i];if(nx>=1&&nx<=n+1&&ny>=1&&ny<=m+1&&(d[nx][ny]==-1||d[nx][ny]>=d[now.ff][now.ss]+1)) {int xx=now.ff+bias_x[i],yy=now.ss+bias_y[i];if(s[xx][yy]==val[i]) {d[nx][ny]=d[now.ff][now.ss];q.push_front(make_pair(nx,ny));}else {d[nx][ny]=d[now.ff][now.ss]+1;q.push_back(make_pair(nx,ny));}}}}if(d[n+1][m+1]==-1) puts("NO SOLUTION");else printf("%d\n",d[n+1][m+1]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！