蒟蒻20分求调
查看原帖
蒟蒻20分求调
352913
123xiayicheng楼主2023/2/6 14:35
#include<bits/stdc++.h>
using namespace std;
int n, m, t, cnt = 0;
int mapn[110][110], inque[110][110], id[110][110];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
struct node
{
	int x, y, time, sum;
} q[110], e, s;
int front = 1, tail = 0;
node make(int x, int y, int time, int sum)
{
	node tmp;
	tmp.x = x;
	tmp.y = y;
	tmp.time = time;
	tmp.sum = sum;
	return tmp;
}
void scan()
{
	char ch[110];
	for (int i = 0; i < n; i++)
	{
		scanf("%s", ch);
		for (int j = 0; j < m; j++)
		{
			if (ch[j] == '.')
				mapn[i][j] = 1;
			else
				mapn[i][j] = 0;
		}
	}
}
void bfs()
{
	memset(inque, 0, sizeof(inque));
	memset(id, 0, sizeof(id));
	q[++tail] = (make(s.x, s.y, 0, 1));
	id[s.x][s.y] = 1;
	inque[s.x][s.y] = 1;
//	front++;
	while (front <= tail)
	{
		node tmp = q[front++];
//		front++;
//    cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.time<<" "<<tmp.sum<<endl;
		inque[tmp.x][tmp.y] = 0;
		
//		for (int i = front; i <= tail; i++)
//		{
//			cout << q[i].x << "," << q[i].y << " " << q[i].time <<" "<<q[i].sum<< "  ";
//		}
//		cout << endl;
//		
		for (int i = 0; i < 4; i++)
		{
			node w=make(tmp.x+dx[i],tmp.y+dy[i],tmp.time+1,tmp.sum);
			int nx = tmp.x + dx[i];
			int ny = tmp.y + dy[i];
			if (w.x == e.x and w.y == e.y and w.time==t)
			{
				cnt += w.sum;
//				cout<<cnt;
				continue;
			}
			if (w.time > t)
			{
				return ;
			}
			if (nx >= 0 and nx<n and  ny >= 0 and ny < m and mapn[nx][ny]==1)
			{
				if (inque[nx][ny] == 1)
					q[id[nx][ny]].sum += w.sum;
				else
					q[++tail] = w, id[nx][ny] = tail, inque[nx][ny] = 1;
			}
		}
	}
}
int main()
{
	cin >> n >> m >> t;
	scan();
	cin >> s.x >> s.y >> e.x >> e.y;
	s.x--;
	s.y--;
	e.x--;
	e.y--;
	bfs();
	cout << cnt;
	return 0;
}
2023/2/6 14:35
加载中...