CF253C Text Editor 题解

思路

既然要求最少步数，那我们可以用bfs

如果鼠标的位置比上一行的行末位置大，如果按上的话，移到上一行的行末。如果鼠标的位置比下一行的行末位置大，如果按下的话，移到下一行的行末。
注

意当鼠标位置超过当前行最大值的时候，要让当前位置去到最大值处。

注意，需要文件读写。

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lhs printf("\n");
using namespace std;
const int N=1e3+10;
const int M=1e5+10;
const int inf=0x3f3f3f3f;
int a[N];
int n;
int sx,sy,ex,ey;
int vis[114][M];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node
{int x,y,step;
};
void bfs(int xx,int yy)
{queue<node> q;vis[xx][yy]=1;q.push(node{xx,yy,0});while(q.size()){node now=q.front();q.pop();	if(now.x==ex and now.y==ey){printf("%d",now.step);return;}for(int i=0;i<4;i++){int nx=now.x+dx[i];int ny=now.y+dy[i];if(ny>=a[nx]){ny=a[nx];}if(nx>=1 and nx<=n and ny>=1 and ny<=a[nx] and vis[nx][ny]==0){vis[nx][ny]=1;q.push(node{nx,ny,now.step+1});}}}
}
int main()
{	freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]++;}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);bfs(sx,sy);return 0;
}

AC记录