题目链接：https://codeforces.com/problemset/problem/1065/D
题意：给你一个又1~n^2组成的n行n列的矩阵，你可以走日字型，直线，斜线，现在要求你从1走到n^2的位置，必须经过1，2，3，4and so on，请问你最短的路径长度和需要变换的方式
题解：非常明显的一个搜索，看了题解后我才明白要用dp存状态。。。。。
这题可以说是一个比较好的把搜索和dp结合起来的题了，首先我们设置dp的状态为，当棋子处于坐标（i，j）时他的当前角色为z，他换了t种角色，并且已经走过前k个点
然后就bfs搜索各种状态即可，首先把三种情况的状态存一下，然后，搜索当前走日字形的情况，搜索当前走直线的情况，搜索当前走斜线的情况，最后遍历所有状态中，走到终点时所有的情况即可
代码如下：
#include #include <set>#include #include #include #include #include #include #include #include <string>#include #include #include <iostream>#include #include #define PI acos(-1)#define eps 1e-8#define fuck(x) cout<<#x<<" = "<#define FIN freopen("input.txt","r",stdin);#define FOUT freopen("output.txt","w+",stdout);//#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;typedef pair<int, int> PII;const int maxn = 1e5 + 5;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}LL lcm(LL a, LL b) { return a / gcd(a, b) * b;}LL powmod(LL a, LL b, LL MOD) { LL ans = 1; while(b) { if(b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2; } return ans;}double dpow(double a, LL b) { double ans = 1.0; while(b) { if(b % 2)ans = ans * a; a = a * a; b /= 2; } return ans;}struct node { int x, y, z, t, k; //x，y 为坐标 //z为当前方式 //t为换了多少次 //k为经过了前k个点 node(int _x, int _y, int _z, int _t, int _k) { x = _x, y = _y, z = _z, t = _t, k = _k; }};int n;int g[15][15];int dp[15][15][3][205][205];////0表示马，1表示车，2表示斜线//int dx1[8][2]={{-2,-1},{-2,1},{2,1},{2,-1},{-1,-2},{-1,2},{1,-2},{1,2}};//int dx2[4][2]={{-1,0},{1,0},{0,1},{0,-1}};//int dx3[4][2]={{-1,-1},{-1,1},{1,1},{1,-1}};int dx1[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}}; //日int dx2[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; //直线int dx3[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; //斜线int sx, sy;int ex, ey;void bfs(int sx, int sy) { memset(dp, -1, sizeof(dp)); dp[sx][sy][0][0][1] = dp[sx][sy][1][0][1] = dp[sx][sy][2][0][1] = 0; queueq; q.push(node(sx, sy, 0, 0, 1)); q.push(node(sx, sy, 1, 0, 1)); q.push(node(sx, sy, 2, 0, 1)); while(!q.empty()) { node nd = q.front(); q.pop(); int x = nd.x, y = nd.y, z = nd.z, t = nd.t, k = nd.k; for(int i = 0; i <3; i++) { if(i == z) continue; if(dp[x][y][i][t + 1][k] != -1) continue; dp[x][y][i][t + 1][k] = dp[x][y][z][t][k] + 1; q.push(node(x, y, i, t + 1, k)); } // cout< if(z == 0) { for(int i = 0; i <8; i++) { int nx = x + dx1[i][0]; int ny = y + dx1[i][1]; int nk = k; if(nx <1 || nx > n || ny <1 || ny > n) continue; if(g[nx][ny] == k + 1) nk++; if(dp[nx][ny][z][t][nk] != -1) continue; dp[nx][ny][z][t][nk] = dp[x][y][z][t][k] + 1; q.push(node(nx, ny, z, t, nk)); } } if(z == 1) { for(int j = 1; j <= 10; j++) { for(int i = 0; i <4; i++) { int nx = x + j * dx2[i][0]; int ny = y + j * dx2[i][1]; int nk = k; if(nx <1 || nx > n || ny <1 || ny > n) continue; if(g[nx][ny] == k + 1) nk++; if(dp[nx][ny][z][t][nk] != -1) continue; dp[nx][ny][z][t][nk] = dp[x][y][z][t][k] + 1; q.push(node(nx, ny, z, t, nk)); } } } if(z == 2) { for(int j = 1; j <= 10; j++) { for(int i = 0; i <4; i++) { int nx = x + j * dx3[i][0]; int ny = y + j * dx3[i][1]; int nk = k; if(nx <1 || nx > n || ny <1 || ny > n) continue; if(g[nx][ny] == k + 1) nk++; if(dp[nx][ny][z][t][nk] != -1) continue; dp[nx][ny][z][t][nk] = dp[x][y][z][t][k] + 1; //q.push(node(nx, ny, z,, y, nk)); q.push(node(nx, ny, z, t, nk)); } } } }}int main() {#ifndef ONLINE_JUDGE FIN#endif cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cin >> g[i][j]; if(g[i][j] == 1) { sx = i; sy = j; } if(g[i][j] == n * n) { ex = i; ey = j; } } } bfs(sx, sy); int ans = INF; for(int z = 0; z <3; z++) { for(int t = 0; t <205; t++) { if(dp[ex][ey][z][t][n * n] != -1) { ans = min(dp[ex][ey][z][t][n * n], ans); } } } int flag = 0; for(int t = 0; t <205; t++) { for(int z = 0; z <3; z++) { if(dp[ex][ey][z][t][n * n] == ans && !flag) { cout <" " < endl; flag = 1; } } }}
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号