Submission #668125
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);
// 周囲で極高でなければ飛ばす
bool flag2 = false;
for (int j = 0; j < 4; j++)
{
// 盤外チェック
if (pos.Key + d[i, 0] + d[j, 0] < 0 || pos.Key + d[i, 0] + d[j, 0] >= N
|| pos.Value + d[i, 1] + d[j, 1] < 0 || pos.Value + d[i, 1] + d[j, 1] >= N) continue;
// 周囲により高いマスがあれば終了
if (a[pos.Key + d[i, 0] + d[j, 0], pos.Value + d[i, 1] + d[j, 1]]
> a[pos.Key + d[i, 0], pos.Value + d[i, 1]])
{
flag2 = true;
break;
}
}
if (flag2)
{
break;
}
// そこを始点に
pos = new Pair(pos.Key + d[i, 0], pos.Value + d[i, 1]);
// リストをクリア
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
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
furuya1223 |
Language |
C# (Mono 4.6.2.0) |
Score |
864553 |
Code Size |
4872 Byte |
Status |
AC |
Exec Time |
770 ms |
Memory |
7512 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
86793 / 100000 |
86213 / 100000 |
86490 / 100000 |
85967 / 100000 |
86518 / 100000 |
86091 / 100000 |
87318 / 100000 |
86299 / 100000 |
86567 / 100000 |
86297 / 100000 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
726 ms |
7512 KB |
subtask_01_02.txt |
AC |
761 ms |
7248 KB |
subtask_01_03.txt |
AC |
732 ms |
7248 KB |
subtask_01_04.txt |
AC |
770 ms |
7248 KB |
subtask_01_05.txt |
AC |
725 ms |
7248 KB |
subtask_01_06.txt |
AC |
681 ms |
7248 KB |
subtask_01_07.txt |
AC |
684 ms |
7248 KB |
subtask_01_08.txt |
AC |
759 ms |
7248 KB |
subtask_01_09.txt |
AC |
711 ms |
7248 KB |
subtask_01_10.txt |
AC |
721 ms |
7248 KB |