Untitled
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...