嵊州普及Day1T2

题意：走迷宫。求走到a[n][n]需要多久。

考场上想的dfs，听老师说最多50分。代码懒得码了，知道是走迷宫就好。

正解：bfs,时间复杂度O（n）。

见代码：

#include<iostream>
using namespace std;
int n,head=0,tail=3,a[1001][1001],h[10001],l[10001],t[10001];
int a1[5]={0,-1,1,0,0},a2[5]={0,0,0,-1,1};
int c1[5]={0,-1,-1,1,1},c2[5]={0,-1,1,-1,1}; 
int flag[1001][1001];
char s;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
       {
           cin>>s;
           a[i][j]=int(s)-int('A')+1;    
           if(a[i][j]==4)
           flag[i][j]=0x3f3f3f3f;
       }
    flag[1][1]=1;
    flag[1][n]=1;
    flag[n][1]=1;
    h[1]=1;
    h[2]=1;
    h[3]=n;
    l[1]=1;
    l[2]=n;
    l[3]=1; 
    while(head!=tail)
    {
        head++;
        int x=h[head],y=l[head];
        if(a[x][y]==1)
        {
            for(int i=1;i<=4;i++)
            {
                if(x+a1[i]>0&&x+a1[i]<=n&&y+a2[i]>0&&y+a2[i]<=n)
                {
                    if(flag[x+a1[i]][y+a2[i]]==0||flag[x+a1[i]][y+a2[i]]>flag[x][y]+1)
                    tail++;
                    h[tail]=x+a1[i];
                    l[tail]=y+a2[i];
                    flag[x+a1[i]][y+a2[i]]=flag[x][y]+1;
                }
            }
        }
        if(a[x][y]==2)
        {
            for(int i=1;i<=4;i++)
            {
                if(x+a1[i]*2>0&&x+a1[i]*2<=n&&y+a2[i]*2>0&&y+a2[i]*2<=n)
                {
                    if(flag[x+a1[i]*2][y+a2[i]*2]==0||flag[x+a1[i]*2][y+a2[i]*2]>flag[x][y]+1)
                    tail++;
                    h[tail]=x+a1[i]*2;
                    l[tail]=y+a2[i]*2;
                    flag[x+a1[i]*2][y+a2[i]*2]=flag[x][y]+1;
                }
            }
        }
        if(a[x][y]==3)
        {
            for(int i=1;i<=4;i++)
            {
                if(x+c1[i]>0&&x+c1[i]<=n&&y+c2[i]>0&&y+c2[i]<=n)
                {
                    if(flag[x+c1[i]][y+c2[i]]==0||flag[x+c1[i]][y+c2[i]]>flag[x][y]+1)
                    tail++;
                    h[tail]=x+c1[i];
                    l[tail]=y+c2[i];
                    flag[x+c1[i]][y+c2[i]]=flag[x][y]+1;
                }
            }
        }
    }
    if(a[n][n]==0)
    cout<<"GO to find Marx";
    else
    cout<<a[n][n];
    return 0;
}

总而言之，相对简单的普及题。

嵊州普及Day1T2

好题哉！！！