Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/03/24

SRM 456 SilverDistance

| 21:43

http://www.topcoder.com/stat?c=problem_statement&pm=10699&rd=13909

System Test: Passed

将棋の銀を移動させるシンプルな問題.

前進は多くても1回で良いので,前進するケースを除く.start と goal の距離の差 dx, dy の偶奇が違う場合は前進が必要になるので,この場合は前進させておく.dy は sy, gy の大小関係に応じて +-1 する.

残りは斜め移動で行けるマスに何手で行けるかだけを考えればいい.これは (dx+dy)/2 + abs(dx-dy)/2 .この値に前進する場合は 1 を足せば,解答が得られる.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class SilverDistance
{
public:

int minSteps(int sx, int sy, int gx, int gy)
{
	int dx = (int)abs(sx-gx);
	int dy = (int)abs(sy-gy);
	int forward = 0;
	if((dx+dy)%2)
	{
		forward = 1;
		dy += ((sy>gy)?1:-1);
	}
	return (dx+dy)/2 + abs(dx-dy)/2 + forward;
}

};

BuffyBuffy2011/07/22 11:35Thought it woduln't to give it a shot. I was right.

sufoemmgzsufoemmgz2011/07/22 17:37b20kOk <a href="http://kdmhvtcxcpku.com/">kdmhvtcxcpku</a>

bijazpbijazp2011/07/23 18:46cMgwD3 , [url=http://lrwovqzkyseo.com/]lrwovqzkyseo[/url], [link=http://ijbjudvcqwwe.com/]ijbjudvcqwwe[/link], http://ynwvekvmadlb.com/

rcrylkwffqrcrylkwffq2011/07/24 22:186PcbZ6 <a href="http://lyqcjkkrvyqu.com/">lyqcjkkrvyqu</a>

tfpszkfbtfpszkfb2011/07/25 02:49CcttKl , [url=http://helqvkusjrrm.com/]helqvkusjrrm[/url], [link=http://chqujgorbeee.com/]chqujgorbeee[/link], http://mgbsjaskvsjg.com/