本文共 1915 字，大约阅读时间需要 6 分钟。

题目地址

题目大意

找出给出的矩阵中cat和girl的数量，单词可以拐弯。

解题思路

很明显是一个bfs的题目，这里我对cat和girl写了两个bfs。
我觉得深搜也是可以做的，因为深度并不会太大。

AC代码

#include <iostream>#include <queue>using namespace std;char s[1100][1100];int book[][2] = {
   {
   1, 0}, {
   -1, 0}, {
   0, 1}, {
   0, -1}};int n, m;struct node{
   	int x, y;	char c;		node (int xx, int yy, char cc)	{
   		x = xx;		y = yy;		c = cc;	}};int bfs(int x, int y, char c){
   	queue <node> que;	int num = 0;		que.push(node(x, y, c));		while (!que.empty())	{
   		node pNode = que.front();		que.pop();				if (pNode.c == 'l')		{
   			num++;			continue;		}				for (int i=0; i<4; i++)		{
   			int tx = pNode.x + book[i][0];			int ty = pNode.y + book[i][1];						if (tx < 0 || ty < 0 || tx >= n || ty >= m)				continue;						if (pNode.c == 'g' && s[tx][ty] == 'i')				que.push(node(tx, ty, 'i'));			else if (pNode.c == 'i' && s[tx][ty] == 'r')				que.push(node(tx, ty, 'r'));			else if (pNode.c == 'r' && s[tx][ty] == 'l')				que.push(node(tx, ty, 'l'));		}	}		return num;}int bfs1(int x, int y, char c){
   	queue <node> que;	int num = 0;		que.push(node(x, y, c));		while (!que.empty())	{
   		node pNode = que.front();		que.pop();				if (pNode.c == 't')		{
   			num++;			continue;		}					for (int i=0; i<4; i++)		{
   			int tx = pNode.x + book[i][0];			int ty = pNode.y + book[i][1];						if (tx < 0 || ty < 0 || tx >= n || ty >= m)				continue;						if (pNode.c == 'c' && s[tx][ty] == 'a')				que.push(node(tx, ty, 'a'));			else if (pNode.c == 'a' && s[tx][ty] == 't')				que.push(node(tx, ty, 't'));		}	}		return num;}int main(){
   	int t;		cin >> t;		while (t--)	{
   		int numg = 0, numc = 0;				cin >> n >> m;				for (int i=0; i<n; i++)			cin >> s[i];				for (int i=0; i<n; i++)		{
   			for (int j=0; j<m; j++)			{
   				if (s[i][j] == 'g')					numg += bfs(i, j, 'g');				else if (s[i][j] == 'c')					numc += bfs1(i, j, 'c');			}		}				cout << numg << " " << numc << endl;	}		return 0;}