题解 P2049 【魔术棋子】

2018-05-07 06:53:34


表示不想写dp....... bfs不照样过去了?

bfs爆搜20分,加了个used数组用来防止点重复入队就AC了?!

代码:

#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;
}