Решение задачи Лиса и две точки с Codeforces

Без пояснения   Просмотров: 1052

Лиса Ciel играет в мобильную игру-головоломку под названием «Две точки». Простейшие уровни играются на доске размера n × m ячеек, выглядящей примерно вот так:

В каждой клетке нарисована точка, обозначенная некоторым цветом. Обозначим различные цвета различными заглавными буквами латинского алфавита.

Задача игрока — найти цикл, состоящий из точек одного цвета. В качестве примера можно рассмотреть обведённые четыре синих точки на картинке. Формально говоря, мы называем последовательность точек d 1, d 2, ..., d k циклом тогда и только тогда, когда выполняются следующие условия:

Это k различных точек: если i ≠ j, то d i отличается от d j.
k не менее 4.
Все точки окрашены в один цвет.
Для всех 1 ≤ i ≤ k - 1: d i и d i + 1 смежные. Также, d k и d 1 тоже должны быть смежные. Ячейки x и y называются смежными, если у них есть общая сторона.
Определите, есть ли на поле цикл.

Код 

#include "bits/stdc++.h"
using namespace std;
 
char a[55][55];
bool v[55][55];
int n,m;
 
void dfs(int x,int y,int w,int z)
{
	if(a[x][y]!=a[w][z])
	return;
	if(v[x][y])
	{
		cout << "Yes";  
		exit(0);
	}
	v[x][y] = true;
	if(x-1>=0&&x-1!=w) dfs(x-1,y,x,y);
	if(y-1!=z&&y-1>=0) dfs(x,y-1,x,y);
	if(y+1<=m&&y+1!=z) dfs(x,y+1,x,y);
	if(x+1!=w&&x+1<=n) dfs(x+1,y,x,y);
}
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;++i)
	{
	    for(int j=0;j<m;++j) cin >> a[i][j]; 
	}
	for(int i=0;i<n;++i)
	{
	    for(int j=0;j<m;++j)
	    {
		    memset(v,false,sizeof(v));
		    dfs(i,j,i,j);
	    }
	}
	cout << "No";
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp