HDOJ水题集合8：DBFS

1001 内蒙创业

内蒙创业
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 52 Accepted Submission(s) : 23
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
莱特与瑞秋毕业了，他们决定在内蒙创业成立一家畜牧业公司，创业第一步：他们希望给公司里的每一只羊一个编号。
编号的命名规则如下：
1.长度为10位；
2.前两位必须为”LQ”；
3.后八位必须为数字；
现在有若干个字符串，希望你写一个程序判断它是不是一个合法编号。
Input
第一行一个T(1≤T≤20)代表数据组数。
每组测试数据有一个字符串s(1≤|s|≤20)，s只包含数字和大写英文字母，代表等待判断的字符串。
Output
如果编号合法输出”YES”，否则输出”NO”。
Sample Input
3
LQ12345678
LQ123
QL12345678
Sample Output
YES
NO
NO

#include<bits/stdc++.h>usingnamespace std;intmain(){int T;  cin>>T;while(T--){
        string s;  cin>>s;if(s.size()==10&&s.substr(0,2)=="LQ"){int ok =1;for(int i =2; i < s.size(); i++)if(!isdigit(s[i]))ok =0;if(ok==1)cout<<"YES\n";else cout<<"NO\n";}else{
            cout<<"NO\n";}}return0;}

1002 挑战棋王丁爸

挑战棋王丁爸
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 24 Accepted Submission(s) : 13
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
一丁三年级的时候学会了跳棋，但一直到现在都没能赢过丁爸（毕竟是棋王~）。

刚好，一丁最近学会了bfs，就打算写一个小程序帮助自己打破零胜的记录。

在一个n*m的矩形棋盘上，一丁想要走动的棋子的坐标是x1,y1,想要棋子到达的坐标是x2,y2。棋子只能往上下左右四个方向走，如果棋子某一方向上相邻的位置没有别的棋子，那就可以直接走一步到达相邻位置，并且走的次数加一，如果走的方向上相邻位置有别的棋子，那也可以直接跳过去，但是只能跳过一个棋子，也就是相当于往一个方向走了两步，并且走的次数还是加一，不过这种情况必须要保证棋子跳到的位置没有别的棋子。

在已知棋盘信息和想要移动的棋子的起点坐标和终点坐标后，一丁希望输出最少走的次数，如果不能走到终点，则输出-1。
Input
题目有多组输入。

每组数据第一行是两个整数n（1<=n<=10）和m(1<=m<=10)，分别表示矩形棋盘的行数和列数。

接下来一共有n行，每行m个字符。只包含‘.’和‘’两种字符。其中，‘.’表示这个位置没有棋子，‘’表示这个位置有棋子。

最后还有一行包含四个正整数x1,y1,x2,y2,分别表示棋子起点的行列坐标和棋子最后想要到达的行列坐标。

题目保证1<=x1,x2<=n, 1<=y1,y2<=m，并且（x1，y1）位置上肯定是‘*’，（x2,y2）上肯定是‘.’。
Output
输出棋子从（x1,y1）到（x2,y2）的最小步数，如果不能到达则输出-1。
Sample Input
3 3
…
..
…
1 1 3 3

3 3
.
…*
**.
1 1 3 3
Sample Output
3
-1

#include<bits/stdc++.h>usingnamespace std;char a[20][20];int d[20][20];int dx[4]={1,-1,0,0};int dy[4]={0,0,-1,1};intmain(){int n, m;while(cin>>n>>m &&n&&m){for(int i =1; i <= n; i++)for(int j =1; j <= m; j++)
                cin>>a[i][j];int sx, sy, ex, ey;
        cin>>sx>>sy>>ex>>ey;memset(d,-1,sizeof(d));;
        d[sx][sy]=0;
        queue<pair<int,int>>q;
        q.push(make_pair(sx,sy));while(q.size()){int x = q.front().first, y = q.front().second;
            q.pop();for(int i =0; i <4; i++){int nx = x+dx[i], ny = y+dy[i];if(nx>=1&&nx<=n && ny>=1&&ny<=m &&a[nx][ny]=='.'&& d[nx][ny]==-1){
                    d[nx][ny]= d[x][y]+1;
                    q.push(make_pair(nx,ny));}elseif(nx>=1&&nx<=n && ny>=1&&ny<=m &&a[nx][ny]=='*'&& d[nx][ny]==-1){
                    nx = nx+dx[i]; ny = ny+dy[i];if(nx>=1&&nx<=n && ny>=1&&ny<=m &&a[nx][ny]=='.'&& d[nx][ny]==-1){
                        d[nx][ny]= d[x][y]+1;
                        q.push(make_pair(nx,ny));}}}}
        cout<<d[ex][ey]<<"\n";}return0;}

1003 条条大路通罗马

条条大路通罗马
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 46 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给定一张通往罗马的地图，地图由0，1组成，1代表罗马的盟国，可走，0代表敌国，不可走（会被当成奸细抓起来）。小明现在被随机传送到了一个国家（x1,y1），他想到罗马(x2,y2)，要求每次只能向右或向下到一个国家，求问从起点到罗马有多少种不同的方案。（数据保证x1<=x2,y1<=y2）
Input
有多组测试数据
每组测试数据第一行两个整数n,m代表地图边界
接下来n行，每行m个数字
接下来一行四个整数代表x1,y1,x2,y2
(1<=n,m<=10,1<=x1,x2<=n,1<=y1,y2<=m)
Output
每组数据一行，代表有多少种不同的方案
Sample Input
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 2 2
Sample Output
2
Author
shenjx
Source
dbfs

#include<bits/stdc++.h>usingnamespace std;int n, m;int a[20][20], vis[20][20];int sx, sy, ex, ey;int ans;int dx[2]={1,0};int dy[2]={0,1};voiddfs(int x,int y){if(x==ex&&y==ey){ans++;return;}if(x<1||x>n || y<1||y>m || a[x][y]==0)return;for(int i =0; i <2; i++){int nx=x+dx[i], ny=y+dy[i];if(!vis[nx][ny]){
            vis[nx][ny]=1;dfs(nx,ny);
            vis[nx][ny]=0;}}}intmain(){while(cin>>n>>m &&n&&m){for(int i =1; i <= n; i++)for(int j =1; j <= m; j++)
                cin>>a[i][j];
        cin>>sx>>sy>>ex>>ey;
        
        ans =0;memset(vis,0,sizeof(vis));;dfs(sx,sy);
        cout<<ans<<"\n";}return0;}

1004 争当图书管理员

争当图书管理员
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 33 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。
每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。
Input
输入包含多组测试用例。
每组数据的第一行，包含两个正整数 n 和 q，以一个空格分开，分别代表图书馆里书的数量和读者的数量。
接下来的 n 行，每行包含一个正整数，代表图书馆里某本书的图书编码。
接下来的 q 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆里读者的需求码的长度，第二个正整数代表读者的需求码。

1 ≤ n ≤ 1,000，1 ≤ q ≤ 1,000，所有的图书编码和需求码均不超过 10,000,000。
Output
每组数据输出 q 行，每行包含一个整数，如果存在第 i 个读者所需要的书，则在第 i 行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出-1。
Sample Input
5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2 12
Sample Output
23
1123
-1
-1
-1
Hint
第一位读者需要的书有 2123、1123、23，其中 23 是最小的图书编码。第二位读者需要的书有 2123、1123，其中 1123 是最小的图书编码。对于第三位，第四位和第五位读者，没有书的图书编码以他们的需求码结尾，即没有他们需要的书，输出-1。
Source
ACM程序设计竞赛实训（甲）- 期末测试

//nq<1e7, 可以暴力#include<bits/stdc++.h>usingnamespace std;int a[1010];intmain(){
    ios::sync_with_stdio(false);int n, q;while(cin>>n>>q &&n&&q){for(int i =1; i <= n; i++)
            cin>>a[i];sort(a+1,a+n+1);while(q--){int len, b;  cin>>len>>b;int t =pow(10,len), ok =0;for(int i =1; i <= n; i++){if((a[i]-b)%t==0){//匹配后缀
                    ok =1;
                    cout<<a[i]<<"\n";break;}}if(ok==0)cout<<"-1\n";}}return0;}