[简单DP] COJ 1122 Game

这道题直接模拟即可，DP相当于一个优化，记录下从第i行第j列出发后到达的最终位置，下次需要时直接取，优化前后最坏情况下复杂度都是O(10^6)。

# include <cstdio>
# include <cstring>
 
# define N 1000 + 5
 
int n, m;
int cnt[N], ff[N], f[N][N];
char g[N][N];
 
int down(int row, int col)
{
    int &ans = f[row][col];
    if (ans != -1) return ans;
    if (row == n) return ans = col;
    if (g[row][col] == '\\')
    {
        if (col+1>m || g[row][col+1]=='/') return ans = 0;
        return ans = down(row+1, col+1);
    }
    if (g[row][col] == '/')
    {
        if (col-1<1 || g[row][col-1]=='\\') return ans = 0;
        return ans = down(row+1, col-1);
    }
    return ans = down(row+1, col);
}
 
void solve(void)
{
    for (int i = 1; i <= n; ++i)
        memset(f[i]+1, -1, sizeof(int)*m);   
    for (int i = 1; i <= m; ++i)
    {
        ff[i] = down(1, i);
        cnt[i] = 0;
    }
    int k, x;
    scanf("%d", &k);
    while (k--)
    {
        scanf("%d", &x);
        ++cnt[ff[x]];
    }
    printf("%d", cnt[1]);
    for (int i = 2; i <= m; ++i)
        printf(" %d", cnt[i]);
    putchar('\n');
}
 
void read_graph(void)
{
    for (int i = 1; i <= n; ++i)
        scanf("%s", g[i]+1);
}
 
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        read_graph();
        solve();
    }   
     
    return 0;
}

2WA，输出时把 n 当作 m 了，还以为是题目的下落方式没理解对。

一组数据：

------------------------input--------------------------------
5 5
_____
_\\__
__/__
_\___
_____
5 1 2 3 4 5

------------------------output------------------------------
1 0 1 2 1