比赛 EYOI与SBOI开学欢乐赛1st 评测结果 AWTTTTWTTT
题目名称 拖拉机 最终得分 10
用户昵称 Skloud 运行时间 7.628 s
代码语言 C++ 内存使用 8.02 MiB
提交时间 2022-08-29 20:44:46
显示代码纯文本
  1. #include<iostream>
  2. #include<fstream>
  3. #include<cmath>
  4. #include<queue>
  5. #include<vector>
  6. using namespace std;
  7. ifstream fin("tractor.in");
  8. ofstream fout("tractor.out");
  9. struct node{
  10. int x,y;
  11. node(){};
  12. node(int a,int b)
  13. {
  14. x=a,y=b;
  15. }
  16. };
  17. queue <node> q;
  18. vector <node> v[3];
  19. int n,x,y,a[1005][1005],c,b;
  20. int maxx=0,maxy=0;
  21. void bfs(node u,int f)
  22. {
  23. q.push(u);
  24. a[u.x][u.y]=f;
  25. v[f].push_back(u);
  26. while(!q.empty())
  27. {
  28. int x=q.front().x,y=q.front().y;
  29. q.pop();
  30. if(a[x+1][y]==0&&x+1<=maxx){
  31. a[x+1][y]=f;
  32. q.push(node(x+1,y));
  33. v[f].push_back(node(x+1,y));
  34. }
  35. if(x-1>=0&&a[x-1][y]==0){
  36. a[x-1][y]=f;
  37. q.push(node(x-1,y));
  38. v[f].push_back(node(x-1,y));
  39. }
  40. if(a[x][y+1]==0&&y+1<=maxy){
  41. a[x][y+1]=f;
  42. q.push(node(x,y+1));
  43. v[f].push_back(node(x,y+1));
  44. }
  45. if(y-1>=0&&a[x][y-1]==0){
  46. a[x][y-1]=f;
  47. q.push(node(x,y-1));
  48. v[f].push_back(node(x,y-1));
  49. }
  50. }
  51. }
  52. int main()
  53. {
  54. fin>>n>>x>>y;
  55. int ans=0x3fffffff;
  56. for(int i=1;i<=n;i++)
  57. {
  58. fin>>c>>b;
  59. a[c][b]=-1;
  60. maxx=max(maxx,c);
  61. maxy=max(maxy,b);
  62. }
  63. maxx++;
  64. maxy++;
  65. bfs(node(x,y),1);
  66. bfs(node(1,1),2);
  67. // for(int i=0;i<=maxx;i++)
  68. // {
  69. // for(int j=0;j<=maxy;j++)
  70. // {
  71. // cout<<a[i][j]<<' ';
  72. // }
  73. // cout<<endl;
  74. // }
  75. for(int i=0;i<v[1].size();i++)
  76. {
  77. for(int j=0;j<v[2].size();j++)
  78. {
  79. // cout<<v[1][i].x<<' '<<v[1][i].y<<' ';
  80. // cout<<v[2][j].x<<' '<<v[2][j].y<<endl;
  81. ans=min(ans,abs(v[1][i].x-v[2][j].x)+abs(v[1][i].y-v[2][j].y)-1);
  82. }
  83. }
  84. fout<<ans<<endl;
  85. return 0;
  86. }