iis7 部署静态网站/搜索引擎有哪些技巧

G

题意：
给你一个n*m的地图，每个点有一个方向，代表在当前点可以往哪个方向走不需要花费能量。现在呢，让你找出最小的修改次数，让小牛可以从11走到nm。同时输出修改的方案，就是在那个点修改成哪个方向。

思考：
当时看到这个题，这改怎么弄呢，没想法，不过前几天做过那个题牛牛走迷宫感觉有一点像，那个题就是让你求出走的路的字典序最小，那我就让dx和dy数组的遍历循序就是从字典序最小的开始遍历就是了，最后输出答案就行。但是这个题呢，让我修改，感觉挺难搞。
这个题就是用了双端队列或者distra，其实双端队列本质还是和distra一样，因为把最小值放在front，最大值放在back。所以这个题就是distra，每次拿取最小值去更新别人。贪心类型的搜索，一个点可以遍历挺多次，只要他可以从更小的地方过来。
有的题目小红的rpg游戏也是让你求最小值，但是呢他还会有别的限制，比如有血量的限制对吧。这就不能用distra了，因为你用distra目的就是只保证距离是最小的，如果你为了距离更小，但是让血变少了，这样会造成达不到终点的结果。所以这种类型题的正解就是对于dist数组要多加一维血量，同时血量的记录也要在queue中记录着，不能用外面的数组记录了，因为你用外面的数组当覆盖的时候覆盖的不止是一个血量的点。然后这种题目一般就不用再vis标记是否更新过了之类的，因为题目本身会限制bfs枚举的次数，当走到这的时候，因为贪心的性质，他不会再回去了。当然还有一种取巧的方法，就是bfs一直去更新，如果血量不为0，就入队，每次出队看看是否为nm，然后每次更新最小值。同时呢，用一个cnt保证，每个点入队不超过10000次。这个次数根据题目来的，随机的。
一般来说，bfs求最短距离一般都不需要标记啊，走过去肯定不会再走回来了，距离变大了，怎么可能会走回来。我傻逼了。
今天又遇到一个类似的题目有始有终，就是让你从初始点走到目的地，每个点有个高度，高度之差小于等于d的都可以直接过去，然后你可以使用魔法，魔法就是可以让一个点的高度为电梯，就是高度可以任意，然后问你从初始点到目标点的最小操作次数是多少。一看就是同类型的题目，只要有多种限制和状态什么的都要放在node里面即可。就用distra跑就行了，把当前点是否变为电梯放到node里，是电梯就为1，不要放在外面。这里有个贪心策略就是a走到b，肯定是让b变成电梯，而不是a变成，因为我想去b，这样b又可以无代价去别人，所以这样是最贪心的。
今天又遇到一个题：Chamber of Secrets。就是给你一个二维数组,(1,1)点往右发射一条激光，有些点是#这些点你可以花费1的代价，使得激光往四周分散。然后让你求出最小的花费使得激光从(n,m)往右边射出去。很明显了，就是类似的最短路。这里我又卡了一下，对于dis有不同的状态，就像小红的rpg游戏，dist数组需要多加一维血量.这里dist[i][j][k]代表，走到i,j。可以往左右射，上下射，上下左右射的不同状态。最后输出答案就行了。

代码：

迷宫2代码：int T,n,m,k;
char va[M][M];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char dir[4] = {'L','R','U','D'};
int dist[M][M],vis[M][M];
PII pre[M][M];void bfs()
{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){vis[i][j] = 0;dist[i][j] = inf;}}deque<PII > q;q.push_back({1,1});dist[1][1] = 0;while(q.size()){auto now = q.front();q.pop_front();int x = now.fi,y = now.se;
//		if(vis[x][y]) continue; //这里有没有都可以，有的话会快一点
//		vis[x][y] = 1;for(int i=0;i<4;i++){int dis = dist[x][y]+(dir[i]!=va[x][y]);int xx = x+dx[i],yy = y+dy[i];if(xx<1||xx>n||yy<1||yy>m) continue;if(dist[xx][yy]>dis){pre[xx][yy] = {x,y};dist[xx][yy] = dis;if(dist[xx][yy]==dist[x][y]) q.push_front({xx,yy});else q.push_back({xx,yy});}}}
}signed main()
{IOS;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>va[i][j];}bfs();cout<<dist[n][m]<<"\n";int x = n,y = m;while(pre[x][y].fi!=0||pre[x][y].se!=0){int xx = pre[x][y].fi,yy = pre[x][y].se;char op;if(xx+1==x) op = 'D';if(xx-1==x) op = 'U';if(yy+1==y) op = 'R';if(yy-1==y) op = 'L';if(va[xx][yy]!=op) cout<<xx<<" "<<yy<<" "<<op<<"\n";x = xx,y = yy;}}return 0;
}迷宫2代码(distra)：struct node{int x,y;int dis;bool operator<(const node&A)const{return A.dis<dis;}
};int T,n,m,k;
char va[M][M];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char dir[4] = {'L','R','U','D'};
int dist[M][M],vis[M][M];
PII pre[M][M];void distra()
{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){vis[i][j] = 0;dist[i][j] = inf;}}priority_queue<node > q;q.push({1,1,0});dist[1][1] = 0;while(q.size()){auto now = q.top();q.pop();int x = now.x,y = now.y;
//		if(vis[x][y]) continue; //这里有没有都可以，有的话会快一点
//		vis[x][y] = 1;for(int i=0;i<4;i++){int dis = dist[x][y]+(dir[i]!=va[x][y]);int xx = x+dx[i],yy = y+dy[i];if(xx<1||xx>n||yy<1||yy>m) continue;if(dist[xx][yy]>dis){pre[xx][yy] = {x,y};dist[xx][yy] = dis;q.push({xx,yy,dis});}}}
}signed main()
{IOS;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>va[i][j];}distra();cout<<dist[n][m]<<"\n";int x = n,y = m;while(pre[x][y].fi!=0||pre[x][y].se!=0){int xx = pre[x][y].fi,yy = pre[x][y].se;char op;if(xx+1==x) op = 'D';if(xx-1==x) op = 'U';if(yy+1==y) op = 'R';if(yy-1==y) op = 'L';if(va[xx][yy]!=op) cout<<xx<<" "<<yy<<" "<<op<<"\n";x = xx,y = yy;}}return 0;
}牛牛走迷宫代码：int T,n,m,k;
char va[M][M];
int vis[M][M];
int dist[M][M];
PII ne[M][M];int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};bool bfs()
{queue<PII > q;q.push({1,1});vis[1][1] = 1;while(q.size()){auto now = q.front();q.pop();int x = now.fi,y = now.se;if(x==n&&y==m) return true;for(int i=0;i<4;i++){int xx = x+dx[i],yy = y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&va[xx][yy]=='0'){vis[xx][yy] = 1;dist[xx][yy] = dist[x][y]+1;ne[xx][yy] = {x,y};q.push({xx,yy});}}}return false;
}signed main()
{IOS;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>va[i][j];}if(!bfs()) cout<<-1;else{int x = n,y = m;vector<char > anw;while(ne[x][y].fi!=0&&ne[x][y].se!=0){int xx = ne[x][y].fi,yy = ne[x][y].se;if(xx+1==x) anw.pb('D');if(xx-1==x) anw.pb('U');if(yy+1==y) anw.pb('R');if(yy-1==y) anw.pb('L');x = xx,y = yy;}reverse(anw.begin(),anw.end());cout<<anw.size()<<"\n";for(auto t:anw) cout<<t;}return 0;
}小红的rpg游戏代码：
struct node{int x,y;int hp;
};int T,n,m,k;
char va[M][M];
int vis[M][M];
int dist[M][M][M];int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};void bfs()
{for(int s=1;s<=k;s++){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)dist[s][i][j] = inf;}}queue<node > q;q.push({1,1,k});dist[k][1][1] = 0;while(q.size()){auto now = q.front();q.pop();int x = now.x,y = now.y,h1 = now.hp;for(int i=0;i<4;i++){int xx = x+dx[i],yy = y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&va[xx][yy]!='*'){int h2 = h1-(va[xx][yy]-'0');if(va[xx][yy]=='.') h2 = h1;if(dist[h2][xx][yy]>dist[h1][x][y]+1&&h2>0){dist[h2][xx][yy] = dist[h1][x][y]+1;q.push({xx,yy,h2});}}}}
}signed main()
{IOS;cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>va[i][j];}bfs();int minn = inf;for(int i=1;i<=k;i++) minn = min(minn,dist[i][n][m]);if(minn==inf) cout<<-1<<"\n";else cout<<minn<<"\n";return 0;
}有始有终代码：
struct node{int x,y;int dis;int is;bool operator<(const node&A)const{return A.dis<dis;}
};int T,n,m,k;
int stx,sty,edx,edy;
int va[M][M];
int vis[M][M];
int dist[M][M];int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};void distra()
{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){vis[i][j] = 0;dist[i][j] = inf;}}priority_queue<node> q;q.push({stx,sty,0});dist[stx][sty] = 0;while(q.size()){auto now = q.top();q.pop();int x = now.x,y = now.y,dis = now.dis;if(vis[x][y]) continue;vis[x][y] = 1;for(int i=0;i<4;i++){int xx = x+dx[i],yy = y+dy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m){int d = abs(va[xx][yy]-va[x][y]);if(now.is) d = k;int w = dis+(d>k);if(dist[xx][yy]>w){dist[xx][yy] = w;q.push({xx,yy,w,(d>k)});}}}}
}signed main()
{IOS;cin>>T;while(T--){cin>>m>>n>>stx>>sty>>edx>>edy>>k;swap(stx,sty),swap(edx,edy);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>va[i][j];}distra();cout<<dist[edx][edy]<<"\n";}return 0;
}Chamber of Secrets代码：struct node{int x,y;int dis;int stx,sty;bool operator<(const node &A)const{return A.dis<dis;}
};int T,n,m,k;
char va[M][M];
int dist[M][M][3];int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};void distra()
{for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<3;k++) dist[i][j][k] = inf;priority_queue<node > q;q.push({1,1,0,1,0});dist[1][1][0] = 0;if(va[1][1]=='#'){q.push({1,1,1,1,1});dist[1][1][3] = 1;}while(q.size()){auto now = q.top();q.pop();int x = now.x,y = now.y,dis = now.dis,stx = now.stx,sty = now.sty;for(int i=0;i<4;i++){int xx = x+dx[i],yy = y+dy[i];if(xx<1||xx>n||yy<1||yy>m) continue;if(i<2&&stx&&dist[xx][yy][0]>dis){dist[xx][yy][0] = dis;q.push({xx,yy,dis,stx,0});}if(i>=2&&sty&&dist[xx][yy][1]>dis){dist[xx][yy][1] = dis;q.push({xx,yy,dis,0,sty});}if(va[xx][yy]=='#'){if(i<2&&stx&&dist[xx][yy][2]>dis+1){dist[xx][yy][2] = dis+1;q.push({xx,yy,dis+1,1,1});}if(i>=2&&sty&&dist[xx][yy][2]>dis+1){dist[xx][yy][2] = dis+1;q.push({xx,yy,dis+1,1,1});}}}}	
}signed main()
{IOS;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>va[i][j];}distra();int minn = min(dist[n][m][0],dist[n][m][2]);if(minn==inf) cout<<"-1\n";else cout<<minn<<"\n";return 0;
}

总结：
对于任何最短路算法，vis标记不标记都无所谓。因为比如第一次b从a转移，a不可能再从b转移了。因为dist[b] = dist[a]+1,dist[a]<dist[b]+1。当然这是在正权图上，如果是负权图，必须加vis和用spfa了。
对于牛牛走迷宫，为什么我加了vis，因为我没初始化dist，如果初始化了dist，dist也只会被更新一次。和加vis标记一样。