见题（非常毒瘤！！！）：
看见此题的第一印象bfs，典型的染色问题，从一个点向四周点扩散，到目标点时停下来，这时一定是最短用时，可一看数据范围，有点大，可还是抱着练好暴力的思想，硬着头皮打下去...细节超级多...打完真的好累，幸好没有细节出什么问题，提交时得了70分，感觉暴力还行...
#include<bits/stdc++.h> using namespace std; int n,m,k,s,x1,yy1,tot,ans; map<int,map<int,int> >vis; map<int,map<int,int> >f; struct node { int x,y,t; }; node a[10000000]; queue<int>q; inline void bfs() { a[++tot].x=x1;a[tot].y=yy1; q.push(tot);vis[x1][yy1]=1; while(!q.empty()) { int o=q.front();q.pop(); int x2=a[o].x; int y2=a[o].y; int t1=a[o].t; if(f[x2][y2]) {ans=t1;return;} if(t1>=s) return; if(y2%2==1&&vis[x2+1][y2+1]!=1&&x2!=n) { a[++tot].x=x2+1; a[tot].y=y2+1; a[tot].t=t1+k; vis[x2+1][y2+1]=1; q.push(tot); } else if(y2%2==0&&vis[x2-1][y2-1]!=1&&x2!=1) { a[++tot].x=x2-1; a[tot].y=y2-1; a[tot].t=t1+k; vis[x2-1][y2-1]=1; q.push(tot); } if(y2!=1&&vis[x2][y2-1]!=1) { a[++tot].x=x2; a[tot].y=y2-1; a[tot].t=t1+k; vis[x2][y2-1]=1; q.push(tot); } if(y2!=2*n-1&&vis[x2][y2+1]!=1) { a[++tot].x=x2; a[tot].y=y2+1; a[tot].t=t1+k; vis[x2][y2+1]=1; q.push(tot); } } } int main() { freopen("1.in","r",stdin); cin>>n>>m>>k>>s; cin>>x1>>yy1; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; f[x][y]=1; } if(f[x1][yy1]) { cout<<s-1<<endl; return 0; } bfs(); if(ans) cout<<s-ans-1<<endl; else cout<<-1<<endl; return 0; }
实在想不到其他思路的我看了看题解：找规律！！！
嗨！下气。
于是乎，就又耐着头皮一点一点突破，终于发现了世纪的谜底...
不想多说什么了，真的好累，这道题搞了我2，3个小时...
#include<bits/stdc++.h> using namespace std; int n,m,k,s,s1,s2,minn=INT_MAX,ans; int main() { freopen("1.in","r",stdin); cin>>n>>m>>k>>s; cin>>s1>>s2; for(int i=1;i<=m;i++) { int x,y; ans=0; cin>>x>>y; if((s2%2==1&&y%2==1)||(s2%2==0&&y%2==0)) { if(s1<x) { int t=x-s1; ans=t*2; if(y>s2+t*2) ans+=y-s2-t*2; else if(y<s2) ans+=s2-y; } else if(x<s1) { int t=s1-x; ans=t*2; if(s2>y+t*2) ans+=s2-y-t*2; else if(s2<y) ans+=y-s2; } else if(x==s1) ans=abs(y-s2); } else { if(s1<x) { int t=x-s1; ans=t*2-1; if(y>s2+t*2-1) ans+=y-s2-t*2+1; else if(y<s2+1) ans+=s2+1-y; } else if(x<s1) { int t=s1-x; ans=t*2-1; if(s2>y+t*2-1) ans+=s2-y-t*2+1; else if(s2<y+1) ans+=y+1-s2; } else if(x==s1) ans=abs(y-s2); } minn=min(minn,ans*k); } if(s-minn-1>=0) cout<<s-minn-1<<endl; else cout<<-1<<endl; return 0; }
代码有点繁琐，鄙人真的不想改了，好累...
启示：
遇到题优先考虑贪心与规律！！！（尤其当出现一些正规的图形时：三角形，正方形，网格呀等等...）
找规律时可以先从特殊点出发，再一步一步发展为普通情况。例如此题，先找从（1，1）到（x，y）的距离，再向一般情况拓展。
原文：https://www.cnblogs.com/gcfer/p/11191911.html