Submission #668755

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}
	Scanner cin;
	const int MOD = 1000000007;
	const int INF = int.MaxValue;
	const double EPS = 1e-7;

	int N = 30;

	void prog()
	{
		cin = new Scanner();

		int[,] a = new int[N, N];
		Pair pos = new Pair();
		int max = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				a[i, j] = cin.nextInt();
				if (a[i, j] > max)
				{
					max = a[i, j];
					pos = new Pair(i, j);
				}
			}
		}
		int[,] d = new int[,] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
		List<Pair> list = new List<Pair>();
		bool[,] visited = new bool[N, N];
		while (max > 0)
		{
			while (true)
			{
				// debug
				//Console.WriteLine("now: {0},{1}", pos.Key + 1, pos.Value + 1);
				
				// 経路に追加
				list.Add(pos);
				visited[pos.Key, pos.Value] = true;

				if (a[pos.Key, pos.Value] - 1 == 0) break;

				bool flag = false;

				// 普通に行けるところを探す
				for (int i = 0; i < 4; i++)
				{
					// 盤外チェック
					if (pos.Key + d[i, 0] < 0 || pos.Key + d[i, 0] >= N
						|| pos.Value + d[i, 1] < 0 || pos.Value + d[i, 1] >= N) continue;
					
					if (a[pos.Key + d[i, 0], pos.Value + d[i, 1]] == a[pos.Key, pos.Value] - 1)
					{
						// debug
						//Console.WriteLine("next: {0},{1}", pos.Key + d[i, 0] + 1, pos.Value + d[i, 1] + 1);
						pos = new Pair(pos.Key + d[i, 0], pos.Value + d[i, 1]);
						flag = true;
						break;
					}
				}
				// 行けるならそのまま行く
				if (flag)
				{
					continue;
				}
				// 普通に行けないなら、隣接する「より高いマス」を探す
				for (int i = 0; i < 4; i++)
				{
					// 盤外チェック
					if (pos.Key + d[i, 0] < 0 || pos.Key + d[i, 0] >= N
						|| pos.Value + d[i, 1] < 0 || pos.Value + d[i, 1] >= N) continue;
					if (visited[pos.Key + d[i, 0], pos.Value + d[i, 1]]) continue;

					// より高いところと隣接してたら
					if (a[pos.Key + d[i, 0], pos.Value + d[i, 1]] >= a[pos.Key, pos.Value])
					{
						// debug
						//Console.WriteLine("reset: {0},{1}", pos.Key + d[i, 0] + 1, pos.Value + d[i, 1] + 1);

						// 極高まで追跡
						Pair next = new Pair(pos.Key + d[i, 0], pos.Value + d[i, 1]);
						while (true)
						{
							// 極高でないフラグ
							bool flag2 = false;
							// 極高チェック
							for (int j = 0; j < 4; j++)
							{
								// 盤外チェック
								if (next.Key + d[j, 0] < 0 || next.Key + d[j, 0] >= N
									|| next.Value + d[j, 1] < 0 || next.Value + d[j, 1] >= N) continue;
								if (visited[next.Key + d[j, 0], next.Value + d[j, 1]]) continue;

								// 周囲により高いマスがあれば
								if (a[next.Key + d[j, 0], next.Value + d[j, 1]]
									> a[next.Key, next.Value])
								{
									next = new Pair(next.Key + d[j, 0], next.Value + d[j, 1]);
									flag2 = true;
									break; ;
								}
							}
							// 極高なら
							if (!flag2)
							{
								break;
							}
						}

						// そこを始点に
						pos = next;
						// リストをクリア
						list.Clear();
						flag = true;
						break;
					}
				}
				// より高い極高マスも無かったら
				if (!flag)
				{
					break;
				}
			}

			// 経路確定・出力
			//Console.WriteLine(list.Count);
			for (int i = 0; i < list.Count; i++)
			{
				a[list[i].Key, list[i].Value]--;
				Console.WriteLine("{0} {1}", list[i].Key + 1, list[i].Value + 1);
			}

			// visited初期化
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < N; j++)
				{
					visited[i, j] = false;
				}
			}

			// リストを空にする
			list.Clear();

			// 最大値を探す
			max = 0;
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < N; j++)
				{
					if (a[i, j] > max)
					{
						max = a[i, j];
						pos = new Pair(i, j);
					}
				}
			}
			//print(a);
		}
	}
	void print(int[,] a)
	{
		Console.WriteLine();
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				Console.Write("{0:00}", a[i, j]);
			}
			Console.WriteLine();
		}
		Console.WriteLine();
	}
}

class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		i = 0;
		return next();
	}

	public int nextInt()
	{
		return int.Parse(next());
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}

}

Submission Info

Judge Result