分类目录归档：算法

洛谷 机器翻译

发表评论

题号：1540

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int m, n;
int head = 0, tail = 0;
int arr[105];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    m++;
    for (int i = 0; i < m; i++){
        arr[i] = -1;
    }
    for (int i = 1; i <= n; i++){
        int word;
        cin >> word;
        bool flag = false;
        for (int i = head; i != tail; i = (i + 1) % m){
            if (arr[i] == word){
                flag = true;
                break;
            }
        }
        if (!flag){
            if (head == (tail + 1) % m)head = (head + 1) % m;
            cnt++;
            arr[tail] = word;
            tail = (tail + 1) % m;
        }
    }
    cout << cnt;
}

洛谷 【模板】最近公共祖先（LCA）

发表评论

调了半天才调出来的东西啊……233，在写tarjan的循环时写错了，把_v_ask写成了_v，太容易写错了，一定要多加注意，这个模版还需要练习，线段树也是。。
Tarjan::

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#define MAXN 1000005
#define MAXM 1000005
#define EdgeLoop(e,node) for(int e=_first[node];e!=-1;e=_next[e])
#define EdgeAskLoop(e,node) for(int e=_first_ask[node];e!=-1;e=_next_ask[e])
int n, m, s;
int _father[MAXN];
int graph_m_ptr = 0, graph_m_ptr_ask = 0;
int _u[MAXN], _v[MAXN], _next[MAXN], _first[MAXN];
bool _visited[MAXN];
int _u_ask[MAXN], _v_ask[MAXN], _next_ask[MAXN], _first_ask[MAXN];
int _ans[MAXM];
int _find(int x){
    if (_father[x] == x)return x;
    return _father[x] = _find(_father[x]);
}
void _merge(int x, int y){//merge y branch to x branch
    _father[_find(x)] = _find(y);
}
void insert_edge(int s, int t){
    _u[graph_m_ptr] = s;
    _v[graph_m_ptr] = t;
    _next[graph_m_ptr] = _first[s];
    _first[s] = graph_m_ptr;
    graph_m_ptr++;
}
void insert_edge_ask(int s, int t){
    _u_ask[graph_m_ptr_ask] = s;
    _v_ask[graph_m_ptr_ask] = t;
    _next_ask[graph_m_ptr_ask] = _first_ask[s];
    _first_ask[s] = graph_m_ptr_ask;
    graph_m_ptr_ask++;
}
void tarjan(int u){
    _visited[u] = true;
    EdgeLoop(e, u){
        if (!_visited[_v[e]]){
            tarjan(_v[e]);
            _merge(_v[e],u);
        }
    }
    EdgeAskLoop(e, u){
        if (_visited[_v_ask[e]]){
            _ans[e/2] = _find(_v_ask[e]);
        }
    }
}
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++){
        _father[i] = i;
    }
    memset(_first, -1, sizeof(_first));
    memset(_first_ask, -1, sizeof(_first_ask));
    for (int i = 1; i <= n - 1; i++){
        int x, y;
        cin >> x >> y;
        insert_edge(x, y);
        insert_edge(y, x);
    }
    for (int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        insert_edge_ask(a, b);
        insert_edge_ask(b, a);
    }
    tarjan(s);
    for (int i = 0; i < m; i++){
        cout << _ans[i] << endl;
    }
}

树上倍增：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
int edge_ptr = 0;
struct edge{
    int v;
    int next;
}edges[1000005];
int head[500005];
int n, m, s;
int father[500005][25],depth[500005];
bool visited[500005];
inline void insert_edge(int s,int t){
    edge_ptr++;
    edges[edge_ptr].v = t;
    edges[edge_ptr].next = head[s];
    head[s] = edge_ptr;
}
inline void dfs(int u){
    visited[u] = true;
    for (int i = 1, len = 1; len <= depth[u]; i++, len <<= 1){
        father[u][i] = father[father[u][i - 1]][i - 1];
    }
    for (int e = head[u]; e != -1;e=edges[e].next){
        if (!visited[edges[e].v]){
            depth[edges[e].v] = depth[u] + 1;
            father[edges[e].v][0] = u;
            dfs(edges[e].v);
        }
    }
}
inline int query(int x, int y){
    if (depth[x] > depth[y])swap(x,y);
    int diff = depth[y] - depth[x];
    for (int i = 0, two = 1; diff != 0; two <<= 1, i++){
        if (diff&two){
            y = father[y][i];
            diff -= two;
        }
    }
    if (x == y)return x;
    for (int i = log2(depth[x]); i >= 0; i--){
        if (father[x][i] != father[y][i]){
            x = father[x][i];
            y = father[y][i];
        }
    }
    return father[x][0];
}
int main(){
    ios::sync_with_stdio(false);
    memset(head, -1, sizeof(head));
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++){
        int x, y;
        cin >> x >> y;
        insert_edge(x, y);
        insert_edge(y, x);
    }
    dfs(s);
    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << endl;
    }
}

洛谷 车站分级

发表评论

题号：P1983
算法标签：拓扑排序
洛谷题解地址：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1983
参考题解：作者: chenshaoqian 更新时间: 2016-09-25 21:08
作者: mangoyang 更新时间: 2016-09-24 17:20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<list>
#include<stack>
using namespace std;
#define virtual_point_start 1000
int n, m;
int s[1005];
int virtual_point_ptr = virtual_point_start;
int indegree[3000];
int pass[1005][1005];
int path_dis[3000];
list<int> edge[3000];
vector<int> t_edge_to;
stack<int> cur_level;
bool execute(){
    while (!cur_level.empty())cur_level.pop();
    for (int i = 1; i <= n; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    for (int i = 1001; i <= virtual_point_ptr; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    if (cur_level.empty())return false;
    while (!cur_level.empty()){
        int cur = cur_level.top();
        cur_level.pop();
        for (list<int>::iterator iter = edge[cur].begin(); iter != edge[cur].end(); iter++){
            indegree[*iter]--;
            int point_dis = (cur <= 1000);
            path_dis[*iter] = max(path_dis[*iter],path_dis[cur] + point_dis);
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)cin >> pass[i][j];
        t_edge_to.clear();
        int ptr = 1;
        for (int j = pass[i][1]; j <= pass[i][s[i]]; j++){
            if (pass[i][ptr] == j)ptr++;
            else t_edge_to.push_back(j);
        }
        virtual_point_ptr++;
        for (vector<int>::iterator iter = t_edge_to.begin(); iter != t_edge_to.end(); iter++){
            edge[virtual_point_ptr].push_back(*iter);
            indegree[*iter]++;
        }
        for (int se = 1; se <= s[i]; se++){
            edge[pass[i][se]].push_back(virtual_point_ptr);
            indegree[virtual_point_ptr]++;
        }
    }
    while (execute());
    int ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, path_dis[i]);
    }
    cout << ans+1;
}

20180814更新：
题解：https://www.luogu.org/blog/24212/solution-p1983
主要是借鉴了一个开一个二维数组判断边是否加重的问题。
还有一个最重要的就是“由停车的站向不停车的站连边”问题，总是考虑不到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool visited[1002][1002];
int inDegree[1002],grades[1002];
vector<int> edges[1002];
vector<int> railStation;
vector<int> unStopStation;
vector<int> curGrade;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        railStation.clear();
        unStopStation.clear();
        int num;
        cin>>num;
        for(int j=1;j<=num;j++){
            int t;
            cin>>t;
            railStation.push_back(t);
        }
        for(int j=0;j<railStation.size()-1;j++){
            for(int k=railStation[j]+1;k<railStation[j+1];k++){
                unStopStation.push_back(k);
            }
        }
        for(int j=0;j<railStation.size();j++){
            for(int k=0;k<unStopStation.size();k++){
                if(visited[railStation[j]][unStopStation[k]])continue;
                visited[railStation[j]][unStopStation[k]]=true;
                edges[railStation[j]].push_back(unStopStation[k]);
                inDegree[unStopStation[k]]++;
            }
        }
    }
    int maxV=0;
    do{
        curGrade.clear();
        for(int i=1;i<=n;i++){
            if(inDegree[i]==0){
                curGrade.push_back(i);
                inDegree[i]--;
            }
        }
        for(int i=0;i<curGrade.size();i++){
            grades[curGrade[i]]++;
            for(int j=0;j<edges[curGrade[i]].size();j++){
                grades[edges[curGrade[i]][j]]=max(grades[edges[curGrade[i]][j]],grades[curGrade[i]]);
                inDegree[edges[curGrade[i]][j]]--;
            }
            maxV=max(maxV,grades[curGrade[i]]);
        }
    }while(curGrade.size());
    cout<<maxV;
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- Chtholly Nota Seniorious

发表评论

洛谷题号：3933
乱搞、二分答案+贪心，根本想不出来，打暴力30分……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int n, m;
int arr[2005][2005];
int arr_rotate[2005][2005];
int pos[2005];
int minnum = 2e9, maxnum = 0;
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] >minnum+value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (maxnum - value > arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
/*check问题搞不懂可以仔细阅读T2题解
check的等效写法：
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] < maxnum - value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (minnum + value < arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
*/
void rotate90degrees(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            arr_rotate[j][n-i+1] = arr[i][j];
        }
    }
    memcpy(arr, arr_rotate, sizeof(arr));
    swap(n, m);
}

int solve(){
    int low = 0, high = maxnum - minnum,mid;
    while (low < high){
        mid = (low + high) / 2;
        if (check(mid)){
            high= mid;
        }
        else{
            low = mid + 1;
        }
    }
    return low;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
            maxnum = max(maxnum,arr[i][j]);
            minnum = min(minnum,arr[i][j]);
        }
    }
    int re = 2e9;
    for (int i = 1; i <= 4; i++){
        re = min(re, solve());
        rotate90degrees();
    }
    cout << re;
    return 0;
}

洛谷 计算系数

发表评论

题号：P1313
大晚上的刷杨辉三角………………

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define MOD 10007
long long arr[1005][1005];
long long a, b, k, n, m;
long long quickpow(long long x, long long y){
    if (y == 0)return 1;
    long long qpsqr2 = quickpow(x, y / 2)%MOD;
    if (y % 2 == 0){
        return (qpsqr2*qpsqr2) % MOD;
    }
    else{
        return (((qpsqr2*qpsqr2) % MOD)*(x%MOD)) % MOD;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b >> k >> n >> m;
    for (int i = 0; i <= 1000; i++){
        arr[0][i] = 1;
        arr[i][i] = 1;
    }
    for (int i = 1; i <= 1000; i++){
        for (int j = 1; j < i; j++){
            arr[j][i] = (arr[j][i - 1] % MOD + arr[j - 1][i - 1] % MOD) % MOD;
        }
    }
    long long ans = arr[n][k];
    ans = (ans*quickpow(a, n)) % MOD;
    ans = (ans*quickpow(b, m)) % MOD;
    cout << ans;
    return 0;
}

20180808更新：
不用杨辉三角啦！因为我会乘法逆元啦！！！哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
#define MOD 10007
ll a,b,k,n,m;
//C(min(n,m),k)*b^m*a^n
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re*re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
int main() {
    cin >> a >> b >> k >> n >> m;
    ll re = (quickpow(a, n)*quickpow(b, m)) % MOD;
    ll cU = 1;
    for (ll i = k; i >= k - min(n, m) + 1; i--) {
        cU *= i % MOD;
        cU %= MOD;
    }
    ll cD = 1;
    for (ll i = 1; i <= min(n, m); i++) {
        cD *= i % MOD;
        cD %= MOD;
    }
    re = ((re * cU) % MOD*inv(cD)) % MOD;
    cout << re;
}

CodeVS 1077 多源最短路 模版

发表评论

从来没写过多源最短路，明天就NOIP初赛了，今天晚上写一下。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
long long arr[105][105];
int n;
long long q;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> arr[i][j];
        }
    }
    for (int k = 1; k <= n; k++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
    cin >> q;
    for (long long i = 1; i <= q; i++){
        int s, e;
        cin >> s >> e;
        cout << arr[s][e] << endl;
    }
    return 0;
}

洛谷 守望者的逃离

发表评论

洛谷题号：P1095
参考题解：作者: 究极龙骑士 更新时间: 2017-07-11 22:44 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1095

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int m, s, t;
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> s >> t;
    int s1 = 0, s2 = 0;//s1跑步,s2瞬间移动
    for (int time = 1; time <= t; time++){
        s1 += 17;
        if (m >= 10){
            m -= 10;
            s2 += 60;
        }
        else{
            m += 4;
        }
        if (s1 < s2)s1 = s2;
        if (s1> s){
            cout << "Yes" << endl << time << endl;
            return 0;
        }
    }
    cout << "No" << endl << s1 << endl;
    return 0;
}

洛谷10月月赛R1·浴谷八连测R1·提高组 SAC E#1 – 一道简单题 Sequence2

发表评论

洛谷题号：P3928
就写60分的代码（仿照LIS），不想写100分（线段树不会）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int n;
long long a[5][100050];//把数列看成4行，原来的第三行分为两行，只能连续大于等于(3)或小于等于(4)，不能转移
long long dp[5][100050];//dp[i][j]表示从第i行选择第j个数的最长波动序列长度
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= 3; i++){
        for (int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++){//将第三行的数复制到第四行
        a[4][i] = a[3][i];
    }
    //dp初始化
    for (int i = 1; i <= 5; i++){
        dp[i][1] = 1;
    }
    //dp转移方程
    for (int j = 2; j <= n; j++){//第j个数
        for (int k = 1; k < j; k++){ //和LIS相同
            //第一行
            for (int i = 1; i <= 4; i++){
                if (a[1][j] >= a[i][k])dp[1][j] = max(dp[1][j], dp[i][k] + 1);
            }
            //第二行
            for (int i = 1; i <= 4; i++){
                if (a[2][j] <= a[i][k])dp[2][j] = max(dp[2][j], dp[i][k] + 1);
            }
            //第三行
            for (int i = 1; i <= 3; i++){
                if (a[3][j] >= a[i][k])dp[3][j] = max(dp[3][j], dp[i][k] + 1);
            }
            //第四行
            for (int i = 1; i <= 4; i++){
                if (i == 3)continue;
                if (a[4][j] <= a[i][k])dp[4][j] = max(dp[4][j], dp[i][k] + 1);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= 4; i++){
        ans = max(ans, dp[i][n]);
    }
    cout << ans << endl;
    return 0;
}

洛谷10月月赛R1·浴谷八连测R1·提高组 SAC E#1 – 一道大水题 Knight

发表评论

洛谷题号：P3930
2017.10.20更新：
有人在洛谷上指出了本程序的错误：测试样例：
5
….X
…..
…..
….B
..O..
存在一种4步的解法。
….4
…..
…3.
….1
..2..
但程序会输出-1。
经过检查，所给出的测试样例中四步解法经过了之前已经经过的点，这种情况是我的程序所无法处理的。因此我的程序存在漏洞，目前还没有想到什么好办法解决。。
原文章：
本来没想着这题能得分，结果这题月赛时竟然80分，后来出题人说有两个点错了，重测就100了。。。/捂脸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int n;
char arr[60][60]; //存放棋子
bool attack[2][60][60]; //某点是否可以被攻击（第一维没有用处，只用了第一维的1）
int dp[60][60];
int O_x, O_y, X_x_pos, X_y_pos;
int K_x[8] = {1,2,2,1,-1,-2,-2,-1};
int K_y[8] = {2,1,-1,-2,-2,-1,1,2};
int X_x[8] = {-1,0,1,-1,1,-1,0,1};
int X_y[8] = {-1,-1,-1,0,0,1,1,1};
inline void render(int x, int y, int no){ //针对坐标为(x,y)的棋子在attack数组中绘制出攻击范围
    switch (arr[x][y]){
    case 'C'://城堡
        for (int i = x + 1; i <= n; i++){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = x - 1; i >= 1; i--){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = y + 1; i <= n; i++){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        for (int i = y - 1; i >= 1; i--){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        break;
    case 'K'://骑士
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                attack[no][x + K_x[i]][y + K_y[i]] = true;
            }
        }
        break;
    case 'B'://主教
        for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
            if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
            else {
                attack[no][x + i][y - i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
            if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
            else{
                attack[no][x + i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
            if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
            else{
                attack[no][x - i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
            if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
            else{
                attack[no][x - i][y - i] = true;
                break;
            }
        }
        break;
    case 'Q'://皇后
        //城堡
        for (int i = x + 1; i <= n; i++){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = x - 1; i >= 1; i--){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = y + 1; i <= n; i++){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        for (int i = y - 1; i >= 1; i--){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        //主教
        for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
            if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
            else {
                attack[no][x + i][y - i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
            if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
            else{
                attack[no][x + i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
            if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
            else{
                attack[no][x - i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
            if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
            else{
                attack[no][x - i][y - i] = true;
                break;
            }
        }
        break;
    case 'X'://国王
        for (int i = 0; i < 8; i++){
            if (x + X_x[i]>0 && x + X_x[i] <= n&&y + X_y[i] > 0 && y + X_y[i] <= n){
                attack[no][x + X_x[i]][y + X_y[i]] = true;
            }
        }
        break;
    case 'P'://普通士兵
        if (x - 1 > 0 && x - 1 <= n&&y + 1 > 0 && y + 1 <= n){
            attack[no][x - 1][y + 1] = true;
        }
        if (x + 1 > 0 && x + 1 <= n&&y + 1 > 0 && y + 1 <= n){
            attack[no][x + 1][y + 1] = true;
        }
        break;
    }
}
inline void render_all(){//将地图上的所有点全部重绘
    memset(attack, false, sizeof(attack));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            switch (arr[i][j]){
            case 'O'://标记好白骑士的起始点
                O_x = i;
                O_y = j;
                break;
            case '.':
            case '\0':
                break;
            case 'X'://黑国王的终止点
                X_x_pos = i;
                X_y_pos = j;
            default:
                render(i, j, 1);
            }
        }
    }
}
void dfs(int x, int y,int step){//记忆化dfs
    if (x <= 0 || y <= 0 || x > n || y > n)return; //超出边界的情况
    if (arr[x][y] == 'X'){ //dfs到了黑国王
        if (step < dp[x][y])dp[x][y] = step;
        return;
    }
    if (attack[1][x][y])return; //刚跳到坐标x,y就被攻击了
    if (step>=dp[x][y])return; //注意，这里是重点，也是为什么DFS不会超时的原因，因为我写的这个DFS记忆化不满足无后效性，所以只要走到一点后，当前步数大于之前走到过这里的最小步数就可以退出了。
    dp[x][y] = step;
    if (arr[x][y] != '.'){ //该格子上有棋子
        char ch = arr[x][y];
        arr[x][y] = '.';
        render_all(); //把棋子吃掉以后重新绘制攻击情况
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                dfs(x + K_x[i], y + K_y[i], step + 1);
            }
        }
        arr[x][y] = ch; //回溯
        render_all();
    }
    else{ //该格子上无棋子
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                dfs(x + K_x[i], y + K_y[i], step + 1);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false); //加快cin速度
    while (cin >> n){ //多组数据
        memset(arr, 0, sizeof(arr));
        memset(attack, false, sizeof(attack));
        memset(dp, 0x7f, sizeof(dp));
        for (int i = 1; i <= n; i++){
            cin >> arr[i] + 1;
        }
        render_all(); //先进行整幅地图攻击情况的绘制
        dfs(O_x, O_y, 0);
        if (dp[X_x_pos][X_y_pos] == 0x7f7f7f7f){
            cout << -1 << endl;
        }
        else{
            cout << dp[X_x_pos][X_y_pos] << endl;
        }
    }
    return 0;
}