C++U5-深度优先搜索-03（记忆化搜索、剪枝和优化）

#include <bits/stdc++.h>
using namespace std;

int t , x , y , mod;//定义
int book[10010][10010]; 
int rem(int x,int y)
{
    if(book[x][y] == -1){
        return -1;
    } 
    if(book[x][y]){
        return book[x][y];//如果之前搜到过
    } 
    book[x][y]=-1; //标记
    if(!x){
         return book[x][y] = 1;
    }
    if(!y){
        return book[x][y]=2;    
    } 
    int num=(x+y)%mod;//num=处理后的x
    return book[x][y]=rem(num,(num+y)%mod);//记忆
}
int main(){
    scanf("%d %d",&t,&mod);//读入
    for(int i = 0 ; i < t ; i++){
        scanf("%d %d",&x,&y); 
        int ans = rem(x , y);//搜索
           //输出
        if(ans == -1){
            cout << "error\n";    
        } 
        else if(ans == 1){
            cout << "1\n";
        } 
        else{
            cout << "2\n";
        } 
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int n , m , a[201][201] , s[201][201] , ans;
bool use[201][201];
int dfs(int x,int y){
    if( s[x][y] ){
        return s[x][y];//记忆 
    }
    s[x][y]=1;//题目中答案是有包含这个点的
    for(int i = 0 ; i < 4 ; i++){  
           int xx = dx[i] + x;
           int yy = dy[i] + y;//四个方向
           if(xx > 0 && yy > 0 && xx <= n && yy <= m && a[x][y] > a[xx][yy]){
                 dfs(xx,yy);
              s[x][y] = max(s[x][y],s[xx][yy]+1);
       }
    }
    return s[x][y];
}
int main()
{    
       scanf("%d%d",&n,&m);//同题目的R,C
       for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            scanf("%d" , &a[i][j]);    
        }
       }   
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            ans = max(ans,dfs(i,j));//取最大值
        }
    }//找从每个出发的最长距离    
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,a[20][20],vis[20],b[20],ans=1600;
void dfs(int t,int sum){
    if(sum>ans) return; //剪枝 
    if(t==n+1){
        //
        ans=min(ans,sum);
        return;
    }
    //坑没填完
    for(int i=1;i<=n;i++){//第t只蚂蚁能选1~n的任务 
        //任务必须没有被选掉
        if(vis[i]==0){ //第t只蚂蚁选了任务i 
            vis[i]=1;
            dfs(t+1,sum+a[t][i]);//轮到下一只蚂蚁
            vis[i]=0; 
        }
         
    } 
} 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    //选任务 
    dfs(1,0);//第一只蚂蚁去选任务 
    cout<<ans;
    return 0;
}