玄关P4667TLE0分求调
  • 板块题目总版
  • 楼主dalu
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/5 13:16
  • 上次更新2025/1/5 19:11:23
查看原帖
玄关P4667TLE0分求调
1416993
dalu楼主2025/1/5 13:16
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;

const int dir[4][2] = {{-1,-1},{-1,1},{1,-1},{1,1}};
const int ab[4] = {2,1,1,2};
const int cd[4][2] = {{-1,-1},{-1,0},{0,-1},{0,0}};
int graph[505][505],dis[505][505];
struct P{int x,y,dis;}u;

int read_ch(){
    char ch;
    while((ch = getchar()) != '/' && ch != '\\');
    return ch == '/' ? 1 : 2;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n,m;
    cin >> n >> m;
    memset(dis,0x3f,sizeof dis);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) graph[i][j] = read_ch();
    deque < P > dq;
    dq.push_back((P){1,1,0});
    dis[1][1] = 0;
    while(!dq.empty()){
        u = dq.front(),dq.pop_front();
        int tx,ty;
        for(int i = 0;i <= 3;i++){
            tx = u.x + dir[i][0],ty = u.y + dir[i][1];
            int d = 0;
            d = graph[u.x + cd[i][0]][u.y + cd[i][1]] != ab[i];
            if(tx && ty && tx < n + 2 && ty < m + 2 && dis[tx][ty] > dis[u.x][u.y] + d){
                dis[tx][ty] = dis[u.x][u.y] + d;
                if(d == 0) dq.push_front((P){tx,ty,dis[tx][ty]});
                else dq.push_back((P){tx,ty,dis[tx][ty]});
                if(tx == n + 1 && ty == m + 1) break;
            }
        }
    }
    if(dis[n + 1][m + 1] != 0x3f3f3f3f) cout << dis[n + 1][m + 1];
    else cout << "NO SOLUTION";
    return 0;
}
2025/1/5 13:16
加载中...