AOJ-1316 : The Sorcerer's Donut

ドーナツ上の物体に呪文が書かれた紙が張り付いている。
ある文字から８方向に移動し続けて、出来る文字列の中から、２回以上出現する最も長い文字列を出力する。複数ある場合は、辞書順比較で最も小さいものを出力する。

ある文字から移動し続けている過程で出てくる文字列も全て対象であることに注意。
スタート地点に戻って来たときに出来た最も長い文字列だけを比較対象にすると間違います。
途中の文字列もしっかり、記憶しておく事。

渡された文字表の移動方法は、モジュロ演算を使うと以外と簡単にできる。

int nx = (x + dx[d] + W) % W;
int ny = (y + dy[d] + H) % H;

この時に、W・H を足して置かないと、値が負の値になったときに、移動がうまく行かなくなるので注意。文字表の移動は上記を用いると良い。

文字列が２回以上出現したかは、mapに保存して出現回数を記憶する。最後はmapを全探索して、2回以上出現した文字列の中で最も大きいものを出力する。


//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1316

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int H,W;
vector< vector<char> > matrix;
map<string,int> spell_map;

int dx[8] = {1,1,0,-1,-1,-1,0,1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};

string mystrcmp(string str1, string str2)
{
	if(str1.length() == str2.length()){
		return (str1 <= str2) ? str1 : str2;
	}else{
		return (str1.length() > str2.length()) ? str1 : str2;
	}
}

void dfs(int sx, int sy, int x, int y, int d, string spell)
{
	int nx = (x + dx[d] + W) % W;
	int ny = (y + dy[d] + H) % H;

	spell_map[spell]++;

	if(nx == sx && ny == sy){ 
		return; 
	}else{
		dfs(sx,sy,nx,ny,d,spell+matrix[ny][nx]);
	}
}

int main()
{
	while(cin >> H >> W && H)
	{
		matrix.assign(H,vector<char>(W));
		spell_map.clear();
		
		rep(h,H){
			rep(w,W){
				cin >> matrix[h][w];
			}
		}

		rep(y,H){
			rep(x,W){
				rep(d,8){
					string str;
					str = str + matrix[y][x];
					dfs( x, y, x, y, d, str);
				}
			}
		}

		string ans;
		for(auto &it : spell_map){
			if(it.second >= 2){
				ans = mystrcmp( ans, it.first );
			}
		}

		cout << ((ans.length() >= 2) ? ans : "0") << endl;
	}
	return 0;
}

kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

AOJ-1316 : The Sorcerer's Donut