1.第一行输入两个整数m,n（m,n<50），之后输入一个m行n列的矩阵，其中0代表空格，1代表白纸，2代表墨水。每经过1秒，墨水会将上下左右相邻的白纸部分染色成墨水，求经过多长时间所有的白纸部分都变成墨水。若不能完全染色，则输出FALSE。
#include <stdio.h> #include <string.h> #include <queue> using namespace std; typedef struct { int val; bool flag; //这个位置是否是本次被染成黑色的 }grid; grid arr[51][51]; int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; int bfs(int m, int n) { bool visit[51][51]; //记录有没有搜索过 memset(visit, 0, sizeof(visit)); queue<pair<int,int>> q; int cnt = 0; for (int i = 1; i <= m; ++i) //找到第一个1或2，从此开始bfs { int j; for (j = 1; j <= n; ++j) { if (arr[i][j].val == 1 || arr[i][j].val == 2) { q.push(pair<int,int>(i,j)); break; } } } if (j <= n) break; while (q.empty() == false) { int t1 = q.front().first; int t2 = q.front().second; if (t1<1 || t2<1 || t1>m || t2>n || visit[t1][t2] == true) { q.pop(); continue; } visit[t1][t2] = true; if (arr[t1][t2].val == 1 || arr[t1][t2].val == 2) { ++cnt; //相邻4个进队列 for (int i = 0; i < 4; ++i) q.push(pair<int, int>(t1 + dir[i][0], t2 + dir[i][1])); } q.pop(); } return cnt; } bool check(int m, int n) //判断是否全部染色 { for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (arr[i][j].val == 1) return false; } } return true; } int main() { int m, n; while (scanf("%d %d", &m, &n) != EOF) { int time = 0; int count = 0; //记录1和2的个数，之后判断是否能连通用 memset(arr, 0, sizeof(arr)); for (int i = 1; i <= m; ++i) //输入 { for (int j = 1; j <= n; ++j) { scanf("%d", &arr[i][j].val); if (arr[i][j].val == 1 || arr[i][j].val == 2) ++count; } } if (bfs(m, n) != count || count == 0) //不可能全部染色 { printf("FALSE\n"); continue; } while (check(m, n) == false) { for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) arr[i][j].flag = false; for (int i = 1; i <= m; ++i) //一次染色的过程 for (int j = 1; j <= n; ++j) if (arr[i][j].val == 2 && arr[i][j].flag == false) for (int k = 0; k < 4; ++k) if (arr[i + dir[k][0]][j + dir[k][1]].val == 1) { arr[i + dir[k][0]][j + dir[k][1]].val = 2; arr[i + dir[k][0]][j + dir[k][1]].flag = true; } ++time; } printf("%d\n", time); } return 0; }2.输入3个字符串，问第三个字符串能否由前两个字符串多次拼接而成。若能，输出前两个字符串分别需要使用几次。若不能则输出FALSE。
#include <string> #include <iostream> using namespace std; //从c串的pos位置开始匹配，use_a是a串的使用次数 bool match(string a, string b, string c, int pos, int &use_a, int &use_b) { if (pos == c.length()) { cout << use_a << " " << use_b << endl; return true; } if (c.substr(pos, a.length()) == a) //尝试用a匹配 { ++use_a; if (!match(a, b, c, pos + a.length(), use_a, use_b)) --use_a; } if (c.substr(pos, b.length()) == b) { ++use_b; if (!match(a, b, c, pos + b.length(), use_a, use_b)) --use_b; } if (c.substr(pos, a.length()) != a && c.substr(pos, b.length()) != b) return false; } int main() { string a, b, c; while (cin >> a >> b >> c) { int use_a = 0, use_b = 0; match(a, b, c, 0, use_a, use_b); if (use_a == 0 && use_b == 0) cout << "FALSE" << endl; } return 0; }