首页 > 代码库 > 【vijos】1791 骑士的旅行（特殊的技巧）
【vijos】1791 骑士的旅行（特殊的技巧）
https://vijos.org/p/1791
暴力的话只想到bfs，然后估计是状态超了才得20分。
噗，为啥暴力就不能想得简单点QAQ。。。。。这种思想很好啊。
这一题我看了题解后不得不说我竟然没想到。。
为啥要bfs。。这种找路径的依赖前边状态的不需要bfs啊！
因为bfs是无限拓展的，状态很大，本题又是8种决策，状态达到8^n啊。。。。sad。。
我们可以这样想，因为状态是向前走的，而且当前状态只依赖于前一个状态，那么我们可以用dp思想啊。。直接枚举当前状态然后看是否根据上一状态到达，标记即可。。
我实在太弱QAQ
（虽然这样做还是暴力，我也没能做出正解，但是这种思想值得写这篇blog，orz
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=40, dx[]={-1, -2, -2, -1, 1, 2, 2, 1}, dy[]={-2, -1, 1, 2, 2, 1, -1, -2};int vis[2][N][N], n, T, X, Y, cnt, a[N][N];int main() { read(n); read(T); read(X); read(Y); for1(i, 1, n) for1(j, 1, n) read(a[i][j]); CC(vis, -1); vis[0][X][Y]=0; int flag=0; for1(t, 1, T) { for1(i, 1, n) for1(j, 1, n) if(t%a[i][j]==0) { rep(k, 8) { int fx=dx[k]+i, fy=dy[k]+j; if(fx<1 || fy<1 || fx>n || fy>n || vis[flag][fx][fy]!=t-1) continue; vis[!flag][i][j]=t; break; } } flag=!flag; } for1(i, 1, n) for1(j, 1, n) if(vis[flag][i][j]==T) ++cnt; printf("%d\n", cnt); for1(i, 1, n) for1(j, 1, n) if(vis[flag][i][j]==T) printf("%d %d\n", i, j); return 0;}
描述
“骑士的旅行”是最近流行的一种棋盘游戏。N*N的棋盘上，我们于时刻0在第X行、 第Y列的格子上放置一个骑士。每个时刻将骑士按照规则进行一步移动，即某个坐标改变2个单位，同时另一个坐标改变1个单位。游戏规则中，棋盘的每个格子并 不总是可以使用的，具体来说，每个格子都被赋予一个正整数，只有当前的时刻是此正整数的倍数时，这个格子才能使用。当然，游戏过程中的每个时刻，骑士必须 处在一个可以使用的格子上。游戏者需要仔细的设计骑士的移动方案才能让游戏进行下去。
给你一个游戏的初始局面，即棋盘的大小，时刻0骑士的位置，以及每个格子被赋予的正整数，请你计算能否对骑士进行T次操作（即游戏能否进行到时刻T）。如果能，请找出时刻T骑士可能出现的所有位置。
格式
输入格式
第1行，包括两个正整数N，T，分别表示棋盘的大小，和操作次数。
第2行，包括两个正整数X, Y，表示时刻0骑士所处的位置。
第3~N+2行，每行N个不超过10^9的正整数。第i+2行的第j个整数表示棋盘上第i行、第j列的格子被赋予的整数。
输出格式
第一行，包含一个非负整数M，表示T次操作后骑士可能出现的位置总数。
接下来M行，每行包括两个正整数，表示一个骑士可能出现的位置。将这些位置按照行编号递增（行编号相同时按列编号递增）的顺序输出。
样例1
样例输入1[复制]
3 21 11 3 22 3 23 1 1
样例输出1[复制]
21 11 3
限制
1s
提示
对于30%的数据，有1 ≤ T ≤ 50,000；
对于100%的数据，有3 ≤ N ≤ 30，1 ≤ T ≤ 1,000,000，1 ≤ X, Y ≤ N。
来源
COCI 2011/2012
【vijos】1791 骑士的旅行（特殊的技巧）