AcWing在线竞赛——第44场竞赛

类比这种，都是一种思想

 for(int i=0;i>a[i];
        if(a[i]>0) b[a[i]]++;
    }
    int num=0;
    for(int i=0;i<=600;i++)
    {
        if(b[i]>0) num++;
    }

简单题聊的差不多了进入下一题

题目的最短路径可理解为除题目输入外的区域为障碍物，则题目给的路线即可能为最短，所以判断题目所给的路线是否为最短共有两个要求：

1.路线不能存在交叉，即不能重复，若重复则非最短路径

2.路线不能相邻，除来的方向之外的三个方向相邻也非最短路径

第一种方式

#include 
#include 
#include 

using namespace std;
const int N = 201,B=N/2;//上下左右四个方向各100，B为开始起点
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//四方向偏移值
bool st[N][N];//定义走过路线的方格
int get(char c)
{
    if(c=='U') return 0;//上0下2左3右1
    if(c=='R') return 1;
    if(c=='D') return 2;
    return 3;
}
int main()
{
    string str;
    cin >> str;
    bool res=true;//定义答案为true
    
    int x=B,y=B;//中心点位置
    st[x][y]=true;//开始格为true
    for(auto c:str)
    {
        int d=get(c);
        x+=dx[d],y+=dy[d];//下个坐标位置
        if(st[x][y]) res=false;//若格子被走过，标记为false
        for(int i=0;i<4;i++)
        if(i!=(d^2)&&st[x+dx[i]][y+dy[i]])//判断是否为相邻格子即判断是否为非来的方向的剩余三个方向相邻
        res=false;//若满足相邻或重复则返回false
        
        st[x][y]=true;
    }
    if(res) cout << "YES";
    else cout << "NO";
    return 0;
}

第二种方式：

个人觉得与第一种类似，该方法为首先给每一格子赋值为1，起始开始后，每一步判断下一步格子的数字多少，若为1，则该格子上下左右都加上1；若大于1，则返回NO

该方法参考了大佬们的思路。

#include 
#include 
#include 
using namespace std;

const int N = 201;
int st[N][N];
string r;
void dx(int x,int y)//定义函数给格子周围加1
{
    st[x][y+1]++;
    st[x][y-1]++;
    st[x][y]++;
    st[x+1][y]++;
    st[x-1][y]++;
}
int main (){
    cin>>r;
    int x=N/2,y=N/2;//中心点
    dx(x,y);
    for(int i=0;i1)
        {
            cout << "NO";
            return 0;
        }
        dx(x,y);
    }
    cout << "YES";
    
}

第三题在能力范围之外了，之后再说吧。

萌新第一次做题解，大佬勿喷<^_^>