Untitled

 avatar
unknown
plain_text
2 years ago
6.9 kB
12
Indexable
Hugo_ditau

#include <iostream>

using namespace std;
int N;
struct node{
	int P;
	int C;
}Door[5];
int check[100];// mang dung de luu gia tri vi nao len cua nao
int Min;
int Q[50000];
int front, rear;
int Door1[100];
int Door2[100];
int Door3[100];
int A[4];
int checkBFS[100]; // Mang dung de check BFS
void Create()
{
	Door1[Door[1].P]  = 1;
	for(int i=Door[1].P; i>1;i--)
		Door1[i-1] = Door1[i]+1;
	for(int i=Door[1].P; i<N;i++)
		Door1[i+1] = Door1[i]+1;

	Door2[Door[2].P]  = 1;
	for(int i=Door[2].P; i>1;i--)
		Door2[i-1] = Door2[i]+1;
	for(int i=Door[2].P; i<N;i++)
		Door2[i+1] = Door2[i]+1;

	Door3[Door[3].P]  = 1;
	for(int i=Door[3].P; i>1;i--)
		Door3[i-1] = Door3[i]+1;
	for(int i=Door[3].P; i<N;i++)
		Door3[i+1] = Door3[i]+1;
}

void BFS_trai(int vt, int dem)
{
	for(int i=0;i<=N;i++) checkBFS[i] = 0;
	front = rear = 0;
	Q[rear] = vt;
	checkBFS[vt] = 1;
	rear++;
	if(check[vt] == 0) 
	{
			check[vt] = vt;
			dem--;
	}
	while (front<rear)
	{
		if(dem==0) return;
		int currentV = Q[front];
		front++;
		int nextTrai = currentV - 1;
		int nextPhai = currentV + 1;
		if(nextTrai > 0 && checkBFS[nextTrai] ==0) 
		{
			if(check[nextTrai] == 0) 
			{
				check[nextTrai] = vt;
				dem--;
			}
			checkBFS[nextTrai] = 1;
			Q[rear] = nextTrai;
			rear++;
		}
		if(dem == 0) return;
		if(nextPhai <= N && checkBFS[nextPhai] ==0) 
		{
			if(check[nextPhai] == 0) 
			{
				check[nextPhai] = vt;
				dem--;
			}
			checkBFS[nextPhai] = 1;
			Q[rear] = nextPhai;
			rear++;
		}
		if(dem==0) return;
	}
}
void BFS_phai(int vt, int dem)
{
	for(int i=0;i<=N;i++) checkBFS[i] = 0;
	front = rear = 0;
	Q[rear] = vt;
	checkBFS[vt] = 1;
	rear++;
	if(check[vt] == 0) 
	{
			check[vt] = vt;
			dem--;
	}
	while (front<rear)
	{
		if(dem==0) return;
		int currentV = Q[front];
		front++;
		int nextTrai = currentV - 1;
		int nextPhai = currentV + 1;
		if(nextPhai <= N && checkBFS[nextPhai]==0) 
		{
			if(check[nextPhai] == 0) 
			{
				check[nextPhai] = vt;
				dem--;
			}
			checkBFS[nextPhai]= 1;
			Q[rear] = nextPhai;
			rear++;
		}
		if(dem == 0) return;
		if(nextTrai > 0 && checkBFS[nextTrai]==0) 
		{
			if(check[nextTrai] == 0) 
			{
				check[nextTrai] = vt;
				dem--;
			}
			checkBFS[nextTrai]= 1;
			Q[rear] = nextTrai;
			rear++;
		}
		if(dem == 0) return;
	}
}
int tinh_KC(int check[])
{
	int sum = 0;
	for(int i=1;i<=N;i++)
	{
		if(check[i] == Door[1].P)
			sum += Door1[i];
		else if(check[i] == Door[2].P)
			sum += Door2[i];
		else if(check[i] == Door[3].P)
			sum+= Door3[i];
	}
	return sum;
}
void Try(int k, int P1, int C1, int P2, int C2, int P3, int C3)
{
	for(int i=0;i<=1;i++)
	{
		A[k] = i;
		if(k==3)
		{
			if(A[1] == 0) BFS_trai(P1,C1);
			else BFS_phai(P1,C1);
			if(A[2] == 0) BFS_trai(P2,C2);
			else BFS_phai(P2,C2);
			if(A[3] == 0) BFS_trai(P3,C3);
			else BFS_phai(P3,C3);
			int sum = tinh_KC(check);
			if(sum<Min) Min = sum;
			for(int i=1;i<=N;i++) check[i] = 0;
		}
		else
			Try(k+1,P1,C1,P2,C2,P3,C3);
	}
}
int main()
{
	freopen("input.txt","r",stdin);
	int tc;
	cin>>tc;
	for(int tci=1;tci<=tc;tci++)	
	{
		cin>>N;
		for(int i=1;i<=3;i++)
		{
			cin>>Door[i].P>>Door[i].C;
		}
		Create();
		//BFS_trai(6,2);
		//BFS_trai(4,5);
		for(int i=1;i<=N;i++) check[i] = 0;
		Min = 999999;
		//1 2 3
		Try(1,Door[1].P,Door[1].C,Door[2].P,Door[2].C,Door[3].P,Door[3].C);
		// 1 3 2
		Try(1,Door[1].P,Door[1].C,Door[3].P,Door[3].C,Door[2].P,Door[2].C);
		// 2 1 3
		Try(1,Door[2].P,Door[2].C,Door[1].P,Door[1].C,Door[3].P,Door[3].C);
		// 2 3 1
		Try(1,Door[2].P,Door[2].C,Door[3].P,Door[3].C,Door[1].P,Door[1].C);
		// 3 1 2
		Try(1,Door[3].P,Door[3].C,Door[1].P,Door[1].C,Door[2].P,Door[2].C);
		// 3 2 1
		Try(1,Door[3].P,Door[3].C,Door[2].P,Door[2].C,Door[1].P,Door[1].C);
		cout<<"Case #"<<tci<<endl<<Min<<endl;
	}
}




Hugo_Bandau
#include <iostream>

using namespace std;

int N,M,rH,cH,pH;
int MaTranKe[100][100];
int check[100][100];
int Q[50000];
int front, rear;
int kq;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

bool checkTren(int rowC,int colC, int rowN, int colN)
{
	if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 3 || MaTranKe[rowC][colC] == 5 || MaTranKe[rowC][colC] == 6) return false;
	if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 2 || MaTranKe[rowN][colN] == 5 || MaTranKe[rowN][colN] == 6) return true;
	else return false;
}
bool checkDuoi(int rowC,int colC, int rowN, int colN)
{
	if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 3 || MaTranKe[rowC][colC] == 4 || MaTranKe[rowC][colC] == 7) return false;
	if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 2 || MaTranKe[rowN][colN] == 4 || MaTranKe[rowN][colN] == 7) return true;
	else return false;
}
bool checkTrai(int rowC,int colC, int rowN, int colN)
{
	if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 2 || MaTranKe[rowC][colC] == 4 || MaTranKe[rowC][colC] == 5) return false;
	if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 3 || MaTranKe[rowN][colN] == 4 || MaTranKe[rowN][colN] == 5) return true;
	else return false;
}
bool checkPhai(int rowC,int colC, int rowN, int colN)
{
	if(MaTranKe[rowN][colN] == 0 || MaTranKe[rowC][colC] == 2 || MaTranKe[rowC][colC] == 6 || MaTranKe[rowC][colC] == 7) return false;
	if(MaTranKe[rowN][colN] == 1 || MaTranKe[rowN][colN] == 3 || MaTranKe[rowN][colN] == 6 || MaTranKe[rowN][colN] == 7) return true;
	else return false;
}
void BFS(int vt)
{
	front = rear = 0;
	int r = vt/M;
	int c = vt%M;
	check[r][c] = 1;
	Q[rear] = vt;
	rear++;
	while (front<rear)
	{
		int currentV = Q[front];
		front++;
		int row = currentV/M;
		int col = currentV%M;
		for(int i=0;i<4;i++)
		{
			int x = row + dx[i];
			int y = col + dy[i];
			if(x<0 || x>=N || y<0 || y>=M) continue;
			else
			{
				if(i==0)
				{
					if(check[x][y] == 0 && checkTren(row,col,x,y)) 
					{
						check[x][y] = check[row][col] + 1;
						Q[rear] = x*M + y;
						rear++;
						if(check[x][y] <=pH) kq++;
					}
				}
				else if(i==1)
				{
					if(check[x][y] == 0 && checkDuoi(row,col,x,y))
					{
						check[x][y] = check[row][col] + 1;
						Q[rear] = x*M + y;
						rear++;
						if(check[x][y] <=pH) kq++;
					}
				}
				else if(i==2)
				{
					if(check[x][y] == 0 && checkTrai(row,col,x,y))
					{
						check[x][y] = check[row][col] + 1;
						Q[rear] = x*M + y;
						rear++;
						if(check[x][y] <=pH) kq++;
					}
				}
				else
				{
					if(check[x][y] == 0 && checkPhai(row,col,x,y))
					{
						check[x][y] = check[row][col] + 1;
						Q[rear] = x*M + y;
						rear++;
						if(check[x][y] <=pH) kq++;
					}
				}
			}
		}
	}
}

int main()
{
	freopen("input.txt","r",stdin);
	int tc;
	cin>>tc;
	for(int tci=1;tci<=tc;tci++)
	{
		cin>>N>>M>>rH>>cH>>pH;
		for(int i=0;i<N;i++)
			for(int j=0;j<M;j++)
			{
				cin>>MaTranKe[i][j];
				check[i][j] = 0;
			}
			kq = 1;
			BFS(rH*M+cH);
			
			/*for(int i=0;i<N;i++)
				for(int j=0;j<M;j++)
				{
					if(check[i][j]>0 && check[i][j]<=pH) kq++;
				}*/
			cout<<"Case #"<<tci<<endl;
			cout<<kq<<endl;
	}
}
Editor is loading...