嵊州D1T2 圣女

嵊州D1T2

圣女

马格里多希望为自己死去却身体不腐的女儿申请圣女。

只是，他不知道神圣的基督教和教皇已经腐朽到了何种地步！

22 年来，他辗转教皇国的各个教堂，但各个教堂都只会以各种理由搪塞、推辞。

教皇国可以看做一个 n ∗ n 的矩形，每个位置都有一个教堂，教堂有不同的种类。教皇所在的位置是 (n, n)，马格里多可以在 (1, 1) (1.n) (n, 1) 中任意一个位置开始自己的旅程。

A 教堂：马格里多可以在牧师的指引下向上/下/左/右任意一个方向移动一格。

B 教堂：马格里多可以在牧师的指引下向上/下/左/右任意一个方向移动两格。

C 教堂：马格里多可以在牧师的指引下向左上/左下/右上/右下任意一个方向移动一格。

D 教堂：贪婪的牧师或者教皇会卷走马格里多的所有财产，使他不能继续自己的旅程。

马格里多经历每个教堂都需要一天的时间。

如果他不能为自己的女儿申请为圣女，请告诉他“Go to find Marx”，否则请告诉他，他的旅程最少需要多少天？

Input

第一行一个整数 n; 接下来 n 行，每行 n 个字母（A, B, C, D）表示教堂的种类。

Output

第一行一个整数表示最少的天数或者“Go to find Marx”(“引号不要输出”)

Examples

saint.in                               saint.out

3 ADC DAC ACA               Go to find Marx

3 AAA CAA AAA                3 

Notes

对于所有数据，满足 n ≤ 1000。

Task1[40pts]

n ≤ 4

Task2[10pts]

只有 A，B 且 B 的个数小于等于 5

Task3[10pts]

没有 D

Task4[40pts]

无特殊限制

---

solve!

这是一道典型的走迷宫的例题，用搜索嘛。

至于是DFS（深搜）还是BFS（广搜），我们有很大很大的争论。

下午讲题时，老师的题解上

所以我要认真研究一下两种搜索，都要！

基本思路

深度优先遍历图的方法是，从图中某顶点v出发：

（1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。　当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS)

首先看顶点：可以从（1，1）（1，n）（n，1）出发。就有了三个v点

再：分别的从v出发，至每一个它的上下左右的教堂。这里就要一个bool数组来标记是否已经访问过了。

A：上下左右全部搜

B：上下左右两格全部搜

C：四个斜角全部搜

D：直接return；

同时，还要不让数组越位

 

//3 AAA CAA AAA
//测试数据
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
char dt[1001][1001];
bool bj[1001][1001],ans=0;
const int inf = 0x3f3f3f;
int n,d=0,day=0,minday=inf;
void jt(int x,int y){//dt[x][y]就是当前那个人在的地方 
    if(!(x>=1&&x<=n&&y>=1&&x<=n)) return;//确保数组不越位 
    if(bj[x][y]) return; 
    bj[x][y]=true;//标记 
    
    bool flag=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        flag=bj[i][j]&&flag;
    if(flag){
        ans=1;
        minday=min(minday,day);
    } 
    //搜索
    if(dt[x][y]=='A')
    {
        day++;
        jt(x+1,y);
        jt(x-1,y);
        jt(x,y+1);
        jt(x,y-1);
        day--;
    }
        if(dt[x][y]=='B')
    {
        day++;
        jt(x+2,y);
        jt(x-2,y);
        jt(x,y+2);
        jt(x,y-2);
        day--;
    }
    if(dt[x][y]=='C')
    {
        day++;
        jt(x+1,y+1);
        jt(x-1,y+1);
        jt(x+1,y-1);
        jt(x-1,y-1);
        day--;
    }
    if(dt[x][y]=='D') return;
    
    bj[x][y]=false;
    return;
}
int main()
{
    //freopen("saint.in","r",stdin);
    //freopen("saint.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        dt[i][j]=getchar();
    }
    jt(1,n);
    jt(1,1);
    jt(n,1);
    if(ans)
        printf("%d",minday);
    else
        printf("Go to find Marx");
    return 0;
}

没问题！

开始的问题嘛，在于忘记先判断dt(地图)[x][y]是否已经被标记过了

OK！