题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
ll n,m,z;
const int N=1010;
ll sk[N][N];
ll dist[N][N];
queue<PII>s;
//清空队列
void clear(queue<PII>&q){
    queue<PII>empty;
    swap(empty,q);
}
int res;
int dx[]={1,0};
int dy[]={0,1};//只能向东或者向南走 
bool vis[N][N];//不可重复 
int bfs(){  
    //各项进行初始处理 
    memset(vis,false,sizeof vis);
    memset(dist,0,sizeof dist);
    clear(s);
    s.push({1,1});
    vis[1][1]=true;
    dist[1][1]=sk[1][1];
    while(!s.empty()){
        PII x=s.front();
        s.pop();
        int r=0,t=0,cc=0;
        vis[x.first][x.second]=false;
        for(int i=0;i<2;i++){
            int xx=x.first+dx[i];
            int yy=x.second+dy[i];
            if(xx>m||yy>z)continue;
            if(dist[xx][yy]<dist[x.first][x.second]+sk[xx][yy]){
               dist[xx][yy]=dist[x.first][x.second]+sk[xx][yy]; 
                s.push({xx,yy});
                vis[xx][yy]=true;
            }
        }
    }
    return dist[m][z]; 
} 
int main(){
    cin>>n;
    while(n--){
    cin>>m>>z;
    memset(sk,0,sizeof sk);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=z;j++){
            cin>>sk[i][j];
        }
    }
    cout<<bfs()<<endl;
    }
    return 0;
}