AOJ - Problem 0071 : Bombs Chain

AOJ DFS

再帰を使って深さ優先探索(DFS)で解くとよいと思います。特に気をつけることはないと思います。

#include <iostream>
#include <string>
using namespace std;

string f[8];
int dx[12] = {0,0,0,-1,-2,-3,0,0,0,1,2,3};
int dy[12] = {-1,-2,-3,0,0,0,1,2,3,0,0,0};

void bomb(int x, int y){
	for(int i=0 ; i < 12 ; i++ ){
		int mx = x + dx[i];
		int my = y + dy[i];
		if( mx < 0 || my < 0 || mx >= 8 || my >= 8 ) continue;
		if( f[my][mx] == '1' ){
			f[my][mx] = '0';
			bomb( mx , my );
		}
	}
}

int main(){
	int n;
	cin >> n;
	for(int t=1 ; t <= n ; t++ ){
		int x,y;

		for(int i=0 ; i < 8 ; i++ ){
			cin >> f[i];
		}
		cin >> x >> y;
		x--;
		y--;
		f[y][x] = '0';
		bomb( x , y );
		cout << "Data " << t << ":" << endl;
		for(int i=0 ; i < 8 ; i++ ){
			cout << f[i] << endl;
		}
	}
}

AOJ ジャンル分けメモ

AOJ

自分のためのAOJの問題の解法ごとのジャンル分けメモです。二番煎じっぽくて緑の人に怒られそうな記事ですがお許しください。
最適な解法とは限りません。難易度順ではなく問題番号順に並んでいます。思い出したときに随時追加します。

ソートする問題

Problem 0001 : List of Top 3 Hills
Problem 0018 : Sorting Five Numbers
Problem 0112 : A Milk Shop
Problem 0124 : League Match Score Sheet
Problem 0161 : Sport Meet
Problem 0533 : Contest
Problem 1043 : Selecting Teams Advanced to Regional
Problem 2198 : Moonlight Farm


素数に関する問題

Problem 0009 : Prime Number
Problem 0044 : Prime Number II
Problem 0053 : Sum of Prime Numbers
Problem 0056 : Goldbach's Conjecture
Problem 0185 : Goldbach's Conjecture II
Problem 0222 : Prime Quadruplet
Problem 1004 : Pair of Primes
Problem 1141 : Dirichlet's Theorem on Arithmetic Progressions

深さ優先探索(DFS)

Problem 0030 : Sum of Integers
Problem 0067 : The Number of Island
Problem 0118 : Property Distribution
Problem 0207 : Block
Problem 0235 : Sergeant Rian
Problem 0535 : Crossing Black Ice
Problem 1130 : Red and Black
Problem 1144 : Curling 2.0
Problem 1160 : How Many Islands?
Problem 2014 : Surrounding Area
Problem 2262 : Stopping Problem


幅優先探索(BFS)

Problem 0121 : Seven Puzzle
Problem 0122 : Summer of Phyonkichi
Problem 0179 : Mysterious Worm
Problem 0193 : Deven-Eleven
Problem 0223 : Stray Twins
Problem 0558 : Cheese
Problem 1166 : Amazing Mazes
Problem 2253 : Brave Force Story


ワーシャルフロイド法(全点対最短路問題)

Problem 0117 : A reward for a Carpenter
Problem 0189 : Convenient Location
Problem 0200 : Traveling Alone: One-way Ticket of Youth
Problem 0526 : Boat Travel
Problem 1134 : Name the Crossing
Problem 2005 : Water Pipe Construction


ダイクストラ法(単一始点最短路問題)

Problem 0212 : Highway Express Bus
Problem 0234 : Aizu Buried Treasure
Problem 1138 : Traveling by Stagecoach
Problem 1150 : Cliff Climbing
Problem 1156 : Twirling Robot


貪欲法(greedy algorithm)

Problem 0521 : Change
Problem 1052 : Old Bridges
Problem 1063 : Watchin' TVA
Problem 2216 : Summer of KMC


動的計画法(DP)

Problem 0042 : A Thief
Problem 0089 : The Shortest Path on A Rhombic Path
Problem 0157 : Russian Dolls
Problem 0168 : Kannondou
Problem 0202 : At Boss's Expense
Problem 0515 : School Road
Problem 0547 : Commute routes
Problem 0557 : A First Grader
Problem 1020 : Cleaning Robot
Problem 2186 : Heian-Kyo Walking
Problem 2254 : Fastest Route
Problem 2272 : Cicada
Problem 2284 : The Legendary Sword