--- 題型 ---

放剩下 相關的題目 ψ(._. )>

---

/*
 * zerojudge
 * h029. 202001_4 貨物分配
 * AC (0.3s, 3MB)
*/
#include<bits/stdc++.h>
using namespace std;

/* limit */
struct LIMIT{
    const long long n = 1e5+1;
    const long long m = 100+1;
}limit;

/* container */
struct T{
    int L;
    int R;
};
int n,m;
vector<int>w(limit.n,0);
vector<int>item(limit.m);
vector<T>g(limit.n);
int p,s,t;

/* function */
int total(int node) {
    if(node>=n){
        return w[node];
    }
    w[node]+=total(g[node].L);
    w[node]+=total(g[node].R);
    return w[node];
}

int loc(int node,int item) {
    if(node>=n){
        w[node]+=item;
        return node;
    }
    if(w[g[node].L]<=w[g[node].R]){
        w[node]+=item;
        return loc(g[node].L, item);
    }else{
        w[node]+=item;
        return loc(g[node].R, item);
    }
}

int main(){
    cin >> n >> m;
    w.resize(2*n+1);
    item.resize(m);
    g.resize(n);
    for(int i=n;i<2*n;++i){
        cin >> w[i];
    }
    for(int i=0;i<m;++i){
        cin >> item[i];
    }
    for(int i=0;i<n-1;++i){
        cin >> p >> s >> t;
        g[p].L=s;
        g[p].R=t;
    }
    //
    total(1);
    for(int i=0;i<m;++i){
        cout << loc(1,item[i]) << " ";
    }
    cout << endl;
}

/*
 * zerojudge
 * d453. 三、最短距離
 * AC (2ms, 308KB)
*/
#include<bits/stdc++.h>
using namespace std;

// URDL
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};

int main(){
    int n;cin>>n;
    while(n--){
        int Y,X,sy,sx,ey,ex;cin>>Y>>X>>sy>>sx>>ey>>ex;
        sx--;sy--;ex--;ey--;
        vector<vector<int>>g(Y,vector<int>(X,0));
        for (int y = 0; y < Y; ++y){
            string s;
            cin >> s;
            for (int x = 0; x < X; ++x){
                g[y][x] = s[x]-'0';
            }
        }
        //
        queue<pair<int, int>> q;
        q.push({sy, sx});
        g[sy][sx] += 1;
        bool found = false;
        while (!q.empty() && !found) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                pair<int, int> front = q.front();
                q.pop();
                int y = front.first;
                int x = front.second;

                if (y == ey && x == ex) {
                    cout << g[y][x] << endl;
                    found = true;
                    break;
                }

                for (int j = 0; j < 4; j++) {
                    int ny = y + dy[j], nx = x + dx[j];

                    if (ny >= 0 && ny < Y && nx >= 0 && nx < X && g[ny][nx] == 0) {
                        g[ny][nx] = g[y][x] + 1; 
                        q.push({ny, nx});
                    }
                }
            }
        }
        if (!found) {
            cout << 0 << endl;
        }
    }
}