【DFS/BFS/再帰】

7795 ワード
問題を記録する
1.DFS+遡及+再帰
POJ盤問題
Description
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の2つの駒を碁盤の中の同じ行または同じ列に置くことができないことを要求する場合は、所定の形状と大きさの碁盤に対して、k個の駒を置くすべての実行可能な配置スキームCをプログラミングして解いてください.
Input
複数セットのテストデータを入力します.各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
Output
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数Cが出力される(データ保証C<2^31).
Sample Input 
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output 
2
1

考え方:DFS+遡及+再帰
#include
#include
#include
using namespace std;
char a[10][10];     //      
int v[10];        //            
int n,k;
int res;    
void DFS(int row,int cnt){//row->    ，cnt->       
    if(cnt>=k){
        res++; return;
    }
    for(int i=row;i

2.BFS+状態圧縮/マーキング
清華-マヤ人のパスワード
タイトルの説明
マヤ人には、文字列に2012の4つの数字が連続して現れるとパスワードを解くパスワードがある.長さNの文字列(2=
説明を入力:
          ，           。
        N，        （2<=N<=13）。
        0、1、2   ，   N    。

出力の説明:
        ，       ，         ；    -1。

例1
入力
5
02120

しゅつりょく
1

考え方:BFS+状態圧縮/タグ
#include 
#include 
#include 
#include 
#include 
using namespace std;
map M;//M[str]  str       
queue Q;//  ，  bfs
 
string Swap(string str, int i){//    i  i+1   
    swap(str[i],str[i+1])
    return newStr=str;
}
 
bool Judge(string str){//          "2012"
    if(str.find("2012", 0)==string::npos) return false;
    else return true;
}
 
int BFS(string str){//      
    string newStr;
    M.clear();//  map
    while(!Q.empty()) Q.pop();//    
    Q.push(str);//             
    M[str]=0;//             0
    while(!Q.empty())
    {
        str=Q.front();
        Q.pop();//    ，  str
        for(int i=0; i>str;//     (    n     )
        if(Judge(str)==true) printf("0
");//          
        else//          ，  bfs
        {
            int ans=BFS(str);
            printf("%d
", ans);
        }
    }
    return 0;//    
}

3.清華-二叉樹遍歴
説明を入力:
     ，   n     26。
        ，        。
                ：A，B，C....  26   。

出力の説明:
         ，        ，
    ，         。

例1
入力
ABC
BAC
FDXEAG
XDEFAG

しゅつりょく
BCA
XEDGAF
#include
#include
using namespace std;
struct Node{
    Node(char c):ch(c){
        r=NULL;
        l=NULL;
    }
    char ch;
    Node *r;
    Node *l;
};
char a[30];
char b[30];
int cnt;
 
Node* recur(int st,int ed){
    if(st>ed||st<0||ed>strlen(a)-1) return NULL;
    int i;
    for(i=st;i<=ed;i++)
        if(a[cnt]==b[i]){
            cnt++;break;
        }
    Node* p  = new Node(b[i]);
    p->l = recur(st,i-1);
    p->r = recur(i+1,ed);
    return p;
}
void hou(Node* rt){
    if(rt!=NULL){
        hou(rt->l);
        hou(rt->r);
        cout<ch;
    }
}
void init(){
    cnt = 0;
}
int main(){
    while(cin>>a>>b){
        init();
        Node* rt = recur(0,strlen(a)-1);
        hou(rt);
        cout<

3.2 D配列のDFS例
説明
地図をn*mの2次元配列で表し、1は陸地を表し、0は海水を表し、各1*1の領域を表す.地図の中の格子は横方向または縦方向にしか接続できず(対角に接続できない)、接続された陸地は島と呼ばれ、地図全体が海水に囲まれている.与えられた地図には島が1つしかなく、島には湖がない(すなわち、水が陸地に囲まれることはない)と仮定します.与えられた2次元地図の島の周長を判断してください.
入力
第1の挙動nおよびmは、地図の大きさ(1<=n<=100、1<=m<=100)を表す.次にn行、各行にm個の数があり、それぞれ1格の数値を記述する.数値の間はスペースで区切られています.
しゅつりょく
島の周長(正の整数)という行しかありません.
サンプル入力
3 4
1 1 1 0
0 1 0 0
1 1 0 0

サンプル出力
14
#include   
#include 
#include 
#include  
#define MN 102
#define INF 0x3f3f3f3f
using namespace std;
int map[MN][MN];
int m,n;
int vis[MN][MN];
int len = 0; 
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1}; //   
void dfs(int x,int y){
	if(x>=0&&x=0&&y>n>>m;
	for(int i=0;i>map[i][j];
	dfs(0,0);
	cout<

4.DFS+記憶化検索(DP思想)
Description
マイケルがスキーが好きなのはおかしくない.スキーは確かに刺激的だからだ.しかし、速度を得るためには、滑る領域を下に傾けなければなりません.そして、坂の底に滑ると、再び上り坂を登ったり、リフトを待ったりしなければなりません.マイケルは1つの領域の中で最も長い底の滑り坂を知りたいと思っています.領域は2 D配列で与えられます.配列の各数値は、点の高さを表します.次に例を示します
 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

1人は、ある点から上下左右に隣接する4つの点の1つにスライドすることができ、高さが減少する場合にのみ.上記の例では、1つの滑り可能な勾配は24〜17〜16である.もちろん25-24-23-...-3-2-1より長い.実は、これは一番長いです.
Input
入力された1行目は、領域の行数Rおよび列数C(1<=R,C<=100)を表す.以下はR行であり、各行にC個の整数があり、高さhを表し、0<=h<=10000である.
Output
最長領域の長さを出力します.
Sample Input 
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output 
25

Source 
/*
       dfs          ,        
                          +1 （dp  ）
           
*/ 
#include
#include
#include
#define MN 102
using namespace std;
int G[MN][MN];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int maxn = 0;
int n,m;
int s[MN][MN];
int vcnt;
int dfs(int x,int y){ //  s[x][y]->(x,y)         
	if(s[x][y]>1) return s[x][y]; //       1，  1     ，   (     ) 
	for(int i=0;i<4;i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&G[x][y]>G[nx][ny]){
			int tmp = dfs(nx,ny)+1;
			if(tmp>s[x][y])
				s[x][y] = tmp;	 //   (     x y   nx ny)                       +1 （dp  ） 
		}
	}
	return s[x][y];	//  s[x][y]
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			scanf("%d",&G[i][j]);
			s[i][j] = 1;		
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			s[i][j] = dfs(i,j);
			if(maxn
ExtJS 5——form提出フォーム
プログラミング練習問題3の明らかな乱数を校正します