UVA-422 题解

正文

♦最坏时间复杂度：\(\mathcal{O}(l^3)\)

由于 \(1\leq l\leq 100\)，\(\mathcal{O}(l^3)\) 可以过。

输入字符阵，枚举 \(i,j\) 指向二维数组中的字符，向八个方向暴力搜索。

可以定义一个方向数组，再定义一个查找函数，这样可以减少码量，方便阅读。

还有一句：特别注意UVA的格式！输出查找结果不要带空格，每个输出后都必须有一个换行！！

代码（附注释）：

#include<iostream>
#include<string>
#define r first
#define o second
using namespace std;
pair<int,int> d[8]{
	{1,1},{1,-1},{-1,-1},{-1,1},
	{1,0},{-1,0},{0,1},{0,-1}
};//方向数组
char c[105][105];//字符数组
int a,b;//用来在f函数中传递字符串末端查找位置
int n;
string s;
bool f(int x,int y,string s){
	if(c[x][y]!=s[0])	return false;//如果第一个字符不匹配，那绝对查找失败
	s.erase(s.begin());//删除头字符，便于后续for范围循环
	for(auto i: d){
		int x1=x,y1=y;
		for(char k: s){
			x1+=i.r,y1+=i.o;//移动查找位置
			if(x1>n||x1<1||y1>n||y1<1)	goto loop;
			if(c[x1][y1]!=k)	goto loop;//如果这个方向匹配失败，跳出循环至loop
		}
		a=x1,b=y1;//如果匹配到，传导末端查找位置
		return true;//匹配成功
		loop: ;//goto大法好
	}
	return false;//若没有匹配的，那最终匹配失败
}
int main(){
	cin>>n;
	bool flag=true;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>c[i][j];//输入字符数组
	while(cin>>s&&s!="0"){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(f(i,j,s)){
					cout<<i<<","<<j<<" "<<a<<","<<b<<"\n";//特别注意UVA的格式！
					if(flag)	flag=false;
					goto down;//goto大法好
				}
		cout<<"Not found\n";
		down: ;
	}
}

洛谷提交记录。

后附

日志

v1.0 on 2022.11.23: 发布