fork(1) 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. 		(($x < $xs) and ($y < $ys) and ($d->[$q] eq $c)) or next;
  29. 		$dd->[$q] = '鐘';
  30. 		$n++;
  31. 	}
  32.  
  33. 	return ($dd, $n);
  34. }
  35.  
  36. sub _f {
  37. 	my ($d, $xs, $ys, $p) = @_;
  38.  
  39. 	my $key = join '', @{$d}[$p .. $#{$d}];
  40. 	defined $memo{$key} and return $memo{$key};
  41.  
  42. 	if ($d->[$p] !~ /[煩悩]/){
  43. 		return $memo{$key} = _f($d, $xs, $ys, $p + 1);
  44. 	}
  45.  
  46. 	my $min = $xs * $ys;
  47. 	foreach(['煩', '悩'], ['悩', '煩']){
  48. 		($d->[$p] eq $_->[0]) or next;
  49.  
  50. 		my ($dd, $n) = __f($d, $xs, $ys, $p, $_->[1]);
  51.  
  52. 		if ($n){
  53. 			$min = min($min, $n + _f($dd, $xs, $ys, $p + 1));
  54. 			$min = min($min, 1 + _f($d, $xs, $ys, $p + 1));
  55. 		}
  56. 		else {
  57. 			$min = min($min, _f($d, $xs, $ys, $p + 1));
  58. 		}
  59. 	}
  60.  
  61. 	return $memo{$key} = $min;
  62. }
  63.  
  64. sub f { _f([map{ split // } @_], length $_[0], scalar @_, 0) }
  65.  
  66. say f(@data);
  67.  
Success #stdin #stdout 0.02s 4028KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
22
https://ideone.com/Fr4eDC
language:
Perl (perl 5.28.1)
created:
10 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!