codeforces_374c
dp[x][y]는 x, y가 도달할 수 있는 최대 깊이를 나타낸다. 만약에 검색할 때마다 원래의 점을 찾을 수 있다면 무한한 것이다.만약 dp[x][y]의 깊이가 4보다 크다면 특정한 열이 존재한다는 것을 의미한다.
AC 코드:
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define max(a,b) ((a) > (b)) ? (a) : (b)
const int MAX_NUMBER = 1003;
int n, m;
char next[] = "DIMA";
char maps[MAX_NUMBER][MAX_NUMBER];
int steps[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int vis[MAX_NUMBER][MAX_NUMBER];
int dp[MAX_NUMBER][MAX_NUMBER];
int find, infi, max_ans;
void dfs(int cnt_x, int cnt_y, char cnt_char) {
if (dp[cnt_x][cnt_y] != -1) {
return ;
}
if (cnt_char == 'A') {
dp[cnt_x][cnt_y] = 1;
find = 1;
}
int next_char;
for (int i = 0; i < 4; i++) {
if (next[i] == cnt_char) {
next_char = i;
break;
}
}
for (int i = 0; i < 4 && !infi; i++) {
int next_x = cnt_x + steps[i][0];
int next_y = cnt_y + steps[i][1];
if (maps[next_x][next_y] == next[(next_char + 1) % 4]) {
if (vis[next_x][next_y]) {
infi = 1;
}
else {
vis[next_x][next_y] = 1;
dfs(next_x, next_y, next[(next_char + 1) % 4]);
dp[cnt_x][cnt_y] = max(dp[cnt_x][cnt_y], dp[next_x][next_y] + 1);
vis[next_x][next_y] = 0;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
memset(maps, 0, sizeof(maps));
for (int i = 1; i <= n; i++) {
scanf("%s", maps[i] + 1);
}
memset(vis, 0, sizeof(vis));
memset(dp, -1, sizeof(dp));
find = infi = max_ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (maps[i][j] == 'D' && !vis[i][j]) {
vis[i][j] = 1;
dfs(i, j, 'D');
if (max_ans < dp[i][j] / 4) {
max_ans = dp[i][j] / 4;
}
vis[i][j] = 0;
}
}
}
if (!find) {
printf("Poor Dima!
");
}
else {
if (infi) {
printf("Poor Inna!
");
}
else {
printf("%d
", max_ans);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.