POJ 3600 Subimage Recognition G++ dfs 巧妙 没掌握

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//英语     看博友分析    抄博友程序      dfs     巧妙      没掌握 
int n1,m1,n2,m2;
char mp1[30][30];
char mp2[30][30];
int a[30];//选择那些列   巧妙 
int num; 
bool check()//没掌握 
{
	int id=0;
	int row=1;
	while(id<n2)
	{
		int i;
		int f=0; 
		for(i=id+1;i<=n2;i++)
		{
			int flag=0;
			for(int j=0,col=1;j<m1;j++,col++)
			{
				if(mp1[row][col]!=mp2[i][a[j]])
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				f=1;
				break;
			}
		}
		if(f==0)
		{
			break;
		}
		row++;
		id=i;
	}
	return row>n1;//抄博友程序 
} 
bool dfs(int index)
{
	if(num==m1)//抄博友程序 
		return check();
	if(index>m2)//抄博友程序 
		return false;
	//删除index列 
	if(dfs(index+1))
		return true;//抄博友程序 
	a[num]=index;
	num++; 
	if(dfs(index+1))
		return true;//抄博友程序 
	num--;
	return false;	
}
int main()
{
	cin>>n1>>m1;
	for(int i=1;i<=n1;i++)
	{
		for(int j=1;j<=m1;j++)
		{
			cin>>mp1[i][j];
		}
	}
	cin>>n2>>m2;
	for(int i=1;i<=n2;i++)
	{
		for(int j=1;j<=m2;j++)
		{
			cin>>mp2[i][j];
		}
	}
	num=0;
	if(dfs(1))
	{
		cout<<"Yes"<<endl;
	}else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

 

本文地址：https://blog.csdn.net/woniupengpeng/article/details/108584979