fork download
copy 
  1. #!/usr/bin/perl
  2. use 5.016;
  3. use warnings;
  4. use utf8;
  5. use List::Util qw(min);
  6.  
  7. chomp(my @data = split /^/, <<'EOF');
  8. 煩悩煩悩煩煩悩煩
  9. 煩煩悩空悩悩悩悩
  10. 悩空悩空悩空悩煩
  11. 空煩煩悩悩悩煩煩
  12. 悩悩悩煩悩煩煩悩
  13. 煩悩空空悩煩悩煩
  14. 煩煩煩悩煩空悩煩
  15. EOF
  16.  
  17. my %memo = ('' => 0);
  18.  
  19. sub __f {
  20. 	my ($d, $xs, $ys, $p, $c) = @_;
  21.  
  22. 	my $n = 0;
  23. 	my $dd = [@{$d}];
  24. 	foreach([1, 0], [-1, 1], [0, 1], [1, 1]){
  25. 		my $x = $p % $xs + $_->[0];
  26. 		my $y = $p / $xs + $_->[1];
  27. 		my $q = $p + $_->[0] + $_->[1] * $xs;
  28. 		(
  29. 			($x >= 0) and ($y >= 0) and ($x < $xs) and ($y < $ys) and 
  30. 			($d->[$q] eq $c)
  31. 		) or next;
  32. 		$dd->[$q] = '鐘';
  33. 		$n++;
  34. 	}
  35.  
  36. 	return ($dd, $n);
  37. }
  38.  
  39. sub _f {
  40. 	my ($d, $xs, $ys, $p) = @_;
  41.  
  42. 	my $key = join '', @{$d}[$p .. $#{$d}];
  43. 	defined $memo{$key} and return $memo{$key};
  44.  
  45. 	if ($d->[$p] !~ /[煩悩]/){
  46. 		return $memo{$key} = _f($d, $xs, $ys, $p + 1);
  47. 	}
  48.  
  49. 	my $min = $xs * $ys;
  50. 	foreach(['煩', '悩'], ['悩', '煩']){
  51. 		($d->[$p] eq $_->[0]) or next;
  52.  
  53. 		my ($dd, $n) = __f($d, $xs, $ys, $p, $_->[1]);
  54.  
  55. 		if ($n){
  56. 			$min = min($min, $n + _f($dd, $xs, $ys, $p + 1));
  57. 			$min = min($min, 1 + _f($d, $xs, $ys, $p + 1));
  58. 		}
  59. 		else {
  60. 			$min = min($min, _f($d, $xs, $ys, $p + 1));
  61. 		}
  62. 	}
  63.  
  64. 	return $memo{$key} = $min;
  65. }
  66.  
  67. sub f { _f([map{ split // } @_], length $_[0], scalar @_, 0) }
  68.  
  69. say f(@data);
  70.  
Success #stdin #stdout 0.02s 3984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
22
https://ideone.com/F4xsSL
language:
Perl (perl 5.28.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!