题解 P2049 【魔术棋子】

表示不想写dp....... bfs不照样过去了？ bfs爆搜20分，加了个used数组用来防止点重复入队就AC了？！ 代码： ```cpp #include <bits/stdc++.h> using namespace std; bool vis[102],used[102][102][102]; int n,m,k,a[102][102],dx[] = {0,1},dy[] = {1,0}; struct Node{int x,y,val;}; int main () { scanf("%d%d%d",&n,&m,&k); for (int i = 0;i < n;i++) for (int j = 0;j < m;j++) scanf("%d",&a[i][j]),a[i][j] %= k;//读入时顺便mod一下 queue<Node> q;q.push({0,0,a[0][0]});//STL的玩意 while (!q.empty())//bfs常规操作 { Node nd = q.front();q.pop();//出队 if (nd.x == n - 1 && nd.y == m - 1) { vis[nd.val] = 1;continue; } for (int i = 0;i < 2;i++) { int nx = dx[i] + nd.x,ny = nd.y + dy[i],nval = a[nx][ny] * nd.val % k; if (nx < 0 || nx >= n || ny < 0 || ny >= m || used[nx][ny][nval]) //最后一步是hash操作 continue; q.push({nx,ny,nval});//出队 used[nx][ny][nval] = 1;//记录点 } } int cnt = 0;//先算一遍个数 for (int i = 0;i < k;i++) cnt += vis[i]; printf("%d\n",cnt); for (int i = 0;i < k;i++) if (vis[i]) printf("%d ",i); return 0; } ```