题解 P2049 【魔术棋子】
SIGSEGV
2018-05-07 06:53:34
表示不想写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;
}
```