# 94,第三个测试点wa了,不知道哪里有问题,bfs双端队列的代码
查看原帖
# 94,第三个测试点wa了,不知道哪里有问题,bfs双端队列的代码
937137
songqi0704楼主2024/3/5 20:34
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define x first
//#define y second
#define int long long
#define PII pair<int,int>
const int  mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int N = 510,M = 1e5+10;
char g[N][N];//存储格内斜边
bool st[N][N];//判重
int d[N][N];//存储操作步数
int n,m;
char es[] = "\\/\\/";//格内斜边,左上角开始顺时针记录
int dx[] = {-1,-1,1,1}, dy[] = {-1,1,1,-1};//格点增量
int ex[] = {-1,-1,0,0}, ey[] = {-1,0,0,-1};//格子增量
void sv(){

}
int bfs(){
    memset(d,0x3f,sizeof d);
    d[0][0] = 0;
    deque<PII> q;
    q.push_back({0,0});
    while(q.size()){
        auto e = q.front();q.pop_front();//队头出队
        int x = e.first, y= e.second;
        if(st[x][y])continue;//已出过队,已最小
        st[x][y] = true;//出队标记,只扩展一次
        for(int i = 0; i < 4; i ++ ){
            int xx = x+dx[i], yy = y+dy[i];//子格点
            if(xx<0||xx>n||yy<0||yy>m)continue;
            int ea = x+ex[i], eb = y+ey[i]; //格子
            int dis = d[x][y]+(g[ea][eb]!=es[i]);
            if(dis<d[xx][yy]){//从(x,y)到(xx,yy)操作更少
                d[xx][yy] = dis;
                if(g[ea][eb]!=es[i])q.push_back({xx,yy});//队尾入队
                else q.push_front({xx,yy});//队头入队
            }
        }
    }
    return d[n][m];
}
void solve() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )cin >> g[i];
    int ans  = bfs();
    if(ans==inf)cout<<"NO SOLUTION"<<endl;
    else cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    setbuf(stdout, NULL);
//    int test;
//    cin >> test;
//    while(test--){sv();}
    solve();

}
2024/3/5 20:34
加载中...