全部RE
  • 板块P1141 01迷宫
  • 楼主Stream_0
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/7/15 11:13
  • 上次更新2023/11/4 14:45:29
查看原帖
全部RE
454499
Stream_0楼主2021/7/15 11:13

自己测没问题,求助。

#include <bits/stdc++.h>
using namespace std;
short mapp[1005][1005];
int n,m = 0;
vector<int> go[1005][1005];
bool vis[1005][1005];
short change[4][2] = {1,0,-1,0,0,1,0,-1};
void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
}
void readMap()
{
	cin >> n >> m;
	char temp;
	for(int y = 1;y <= n;y ++)
	{
		for(int x = 1;x <= n;x ++)
		{
		 	scanf("%c",&temp);
		 	mapp[x][y] = temp - '0';
		}
		scanf("%c",&temp);
	}
}
void printMap()
{
	for(int y = 1;y <= n;y ++)
	{
		for(int x = 1;x <= n;x ++)
		{
		 	cout << mapp[x][y];
		}
		cout << endl;
	}
}
long long dfs(int x,int y)
{
	if(x<1 || x>n || y<1 || y>n)
	{
		return 0;
	}
	//cout << "-----------\n";
	//cout << "now dfs position:" << x << ' ' << y << endl;
	vis[x][y] = true;
	long long ret = 0;
	for(int i = 0;i < 4;i ++)
	{
		int newx = x + change[i][0];
		int newy = y + change[i][1];
		if(!vis[newx][newy] && mapp[x][y]+mapp[newx][newy]==1)
		{
			vector<int> v;
			v.push_back(x);
			v.push_back(y);
			go[newx][newy] = v;
			ret += dfs(newx,newy);
		}
	}
	return ret + 1;
}
string toString(vector<int> v)
{
	stringstream s;
	for(int i = 0;i < v.size();i ++)
	{
		s << v[i];
		s << ' ';
	}
	return s.str();
}
long long answer(int x,int y)
{
	//cout << "-----------\n";
	if(go[x][y].size() == 2)
	{
		vector<int> father;
		father = go[x][y];
		//cout << "memorial:now at " << x << ' ' << y  << ' ' << "with father value" << toString(father) << endl;
		while(father.size() == 2)
		{
			father = go[father[0]][father[1]];
			//cout << "memorial:now at father value" << toString(father) << endl;
		}
		return father[0];
	}
	else
	{
		//cout << "new block:now at " << x << ' ' << y << '\n';
		vector<int> father;
		int ret = dfs(x,y);
		father.push_back(ret);
		go[x][y] = father;
		return ret;
	}
}
int main()
{
	init();
	readMap();
	//printMap();
	int a,b;
	for(int i = 0;i < m;i ++)
	{
		cin >> a >> b;
		cout << answer(b,a) << endl;
	}
	return 0;
}
2021/7/15 11:13
加载中...