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