SCOLLECT - Trò chơi nhặt quà

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int f[260][130][130];
char a[130][130];
bool reach[130][130];
int m,n;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

void DFS(int x,int y)
{        
    for (int i = 0; i < 4; i++)
    {
        int px = x + dx[i],py = y + dy[i];
        if (px < 0 || px >= m || py < 0 || py >= n || reach[px][py] || a[px][py] == '#') continue;
        reach[px][py] = true;
        DFS(px,py);
    }
}

int rec(int step,int x,int y)
{
    if (f[step][x][y] > -1) return f[step][x][y];
    if (step == m + n - 1) return f[step][x][y] = 0;
    int best = 0;
    for (int px = 0; px < 2; px++)
      for (int py = 0; py < 2; py++)
      {
            int tx = x + px,ty = y + py;
            int sx = step + 1 - tx,sy = step + 1 - ty;
            if (tx > ty || ty >= n || sx >= m || a[sx][tx] == '#' || a[sy][ty] == '#') continue;
            int tmp = rec(step + 1,tx,ty);
            if (a[sx][tx] == '*') tmp++;
            if (ty > tx && a[sy][ty] == '*') tmp++;
            best = max(best,tmp);
        }
    return f[step][x][y] = best;
}

int main()
{
//    freopen("tour.in","r",stdin);
//    freopen("tour.ou","w",stdout);
    
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        while (1)
        {
            scanf("%c", &a[i][j]);
            if (a[i][j] == '.' || a[i][j] == '*' || a[i][j] == '#') break;
        }
    memset(f,-1,sizeof(f));
    memset(reach,false,sizeof(reach));
    if (a[0][0] != '#') 
    {
        reach[0][0] = true; DFS(0,0);
    }
    if (!reach[m - 1][n - 1]) printf("0\n"); else
    printf("%d\n", ((a[0][0] == '*') ? 1 : 0) + rec(0,0,0));
}

Download