时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Recently Little Hi started to like astronomy and downloaded the pictures of K constellations. He wonders how many of them he can spot in the night?
输入
Line 1: K(1 <= K <= 20), the number of constellations.K constellation pictures follow. The format of each picture is:Line 1 of each picture: H and W(5 <= H, W, <= 100), the height and width of the picture.Line 2~H+1 of each picture: An H*W matrix of characters representing the picture of a constellation. Each line contains W characters. ‘#’ for a star and ‘.’ for empty area. There are no more than 20 stars in each constellation.After K constellations is the sky Little Hi looks to in the night.Line 1 of sky: N and M(100 <= N, M <= 1000), the size of the sky Little Hi looks to.Line 2~N of sky: An N*M matrix of characters representing the sky Little Hi looks to. Each line contains M characters. ‘#’ for a star and ‘.’ for empty area. There are no more than 5000 stars in the sky.
输出
For each constellation in the Input output "Yes" or "No" indicating whether Little Hi can spot the constellation in the sky.All pictures of constellations and the sky Little Hi looks to are in the same direction so there is no need to rotate the pictures.
提示
A constellation can be spoted if and only if all stars in the constellation can be matched in the sky. It is allowed that two spoted constellations share common stars.
样例输入35 5#…………#…….#…5 5….#……….#……..#5 6…..#……#……………#.10 10…….#…………..#…………………..#…………………….#………….#………….样例输出NoYesYes最初的错误想法是从sky的那个矩阵的(0,0)端点开始依次与上面的小picture做比较。
小picture的第一行与sky的(0,0)开始，长度为picture一行的长度做比较，如果一致，则将picture第二行与sky(1，0)比较，这样一直纵向比较下去，直到picture的第n行与sky（n，0）不相等为止。
对于不相等的情况，恢复到之前纵向比较的位置，并向右移一位，与picture第一行做比较。
保证以后再也不贴错误代码了。。。好不容易写出这么大段，舍不得%>_<%
#include <iostream>#include <string>#include <vector>using namespace std;int main(){int k;cin >> k;vector<vector<string>>con;while (k–){vector<string>tmp;int w, h;cin >> w >> h;char a;for (int i = 0; i < w; i++){string s;cin >> s;tmp.push_back(s);}con.push_back(tmp);}int w1, h1;cin >> w1 >> h1;char b;vector<string>finc;vector<vector<int>>visit;for (int i = 0; i < w1; i++){string ss;cin >> ss;finc.push_back(ss);}int flag;for (int i1 = 0; i1 < con.size(); i1++){visit.clear();for (int i = 0; i < w1; i++){vector<int>v1;for (int j = 0; j < h1; j++){v1.push_back(0);}visit.push_back(v1);}vector<string>tmp = con[i1];int row = 0;int count_row = -1;flag = 0;for (int i = 0;i < finc.size()-tmp.size()+1; i++){if (i >= finc.size())break;for (int j = 0; j < w1 – tmp[0].size() + 1;){if (i >= finc.size())break;//cout << "i,j " << i << " " << j << endl;if (visit[i][j] == 0){if (tmp[row] == finc[i].substr(j, tmp[row].size())) //怎么可以直接比较呢{visit[i][j] = 1;if (row == 0){//cout << "row=0, i= " << i << endl;count_row = i;//记录纵向比较时最初的行数}i++;row++;if (row == tmp.size())//比较到最后一行也相等的则输出YES{flag = 1;break;}}else{visit[i][j] = -1;j++;row = 0;if (count_row != -1){i = count_row;//恢复纵向比较最初的行数count_row = -1;}if (j == finc[0].size() – tmp[0].size() + 1){j = 0;i++;}}}elsej++;}if (flag == 1){cout << "Yes" << endl;break;}}if (flag!=1)cout << "No" << endl;}system("pause");return 0;}忽视了一个重大问题好么！！！！那些星座之间有可能重叠的好么，不仅仅是共用某个星星。所以这样依次比较string是否完全相等根本就是错误的好么！！！
然后修改了两个字符串比较的函数。
bool star_com(string a, string b){int len = a.size();for (int i = 0; i < len; i++){if (a[i] == '#'){if (b[i] != '#')return false;}}return true;}
稍微改了一下变成这个样子
#include <iostream>#include <string>#include <vector>using namespace std;bool star_com(string a, string b){int len = a.size();for (int i = 0; i < len; i++){if (a[i] == '#'){if (b[i] != '#')return false;}}return true;}int main(){int k;cin >> k;vector<vector<string>>con;while (k–){vector<string>tmp;int w, h;cin >> w >> h;char a;for (int i = 0; i < w; i++){string s;cin >> s;tmp.push_back(s);}con.push_back(tmp);}int w1, h1;cin >> w1 >> h1;char b;vector<string>finc;for (int i = 0; i < w1; i++){string ss;cin >> ss;finc.push_back(ss);}int flag;for (int i1 = 0; i1 < con.size(); i1++){vector<string>tmp = con[i1];int row = 0;int count_row = -1;flag = 0;for (int i = 0; i < finc.size() – tmp.size() + 1; i++){if (i >= finc.size())break;for (int j = 0; j < w1 – tmp[0].size() + 1;){if (i >= finc.size())break;if (star_com(tmp[row], finc[i].substr(j, tmp[row].size()))){if (row == 0)count_row = i;i++;row++;if (row == tmp.size()){flag = 1;break;}}else{j++;row = 0;if (count_row != -1){i = count_row;count_row = -1;}if (j == finc[0].size() – tmp[0].size() + 1){j = 0;i++;}}}if (flag == 1){cout << "Yes" << endl;break;}}if (flag != 1)cout << "No" << endl;}system("pause");return 0;}
很好，现在变超时了。。。。(╯‵□′)╯︵┻━┻ 能否告诉我怎样优化！！！
看来要全部重写了，这就是题目条件利用不充分的后果。
看里面的数据都不大，对前面的小图保存于第一个星星的相对位置。然后在便利sky时，对里面的每个点都依次视为第一个小图的第一星星，，然后对比其他星星的吻合情况。
不付出，却一定不会有收获，不要奢望出现奇迹。
