Untitled
unknown
plain_text
2 years ago
5.0 kB
6
Indexable
#include <iostream>
using namespace std;
int T, N, G, map[20][20], xG, yG, isGold[20][20], ans;
int arr[20][20][4], cnt;
int front, rear, visit[20][20];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
//int maxx, movang2, movangMax, Min = 1000000, ee = -1, ff = -1;
struct Node{
int x, y;
};
Node gold[4];
Node queue[400];
void en(int x, int y){
Node node; node.x = x; node.y = y;
rear++;
queue[rear] = node;
}
Node de(){
return queue[++front];
}
void reset(){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
isGold[i][j] = 0;
visit[i][j] = 0;
for(int k = 0; k < G; k++){
arr[i][j][k] = -1;
}
}
}
}
void resetVisit(){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
visit[i][j] = 0;
}
}
}
void bfs(int x, int y){
en(x, y); visit[x][y] = 1;
while(front != rear){
Node node = de();
for(int k = 0; k < 4; k++){
int r = node.x + dx[k];
int c = node.y + dy[k];
if(r >= 0 && r < N && c >= 0 && c < N && map[r][c] != 0 && visit[r][c] == 0){
en(r, c);
visit[r][c] = visit[node.x][node.y] + 1;
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
reset();
cin >> N >> G;
for(int i = 0; i < G; i++){
cin >> xG >> yG;
xG--; yG--;
gold[i].x = xG; gold[i].y = yG;
isGold[xG][yG] = 1;
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> map[i][j];
visit[i][j] = 0;
}
}
int Min = 1000000;
int maxx = 0, movang2 = 0 , movangMax = 0, ee = -1, ff = -1;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(map[i][j] == 1 && isGold[i][j] == 0){
resetVisit();
front = rear = -1;
bfs(i, j);
cnt = 0;
maxx = 0; movang2 = 0;
bool check = true;
for(int g = 0; g < G; g++){
cnt = visit[gold[g].x][gold[g].y];
if(cnt == 0){
check = false;
break;
}
}
if(check==true){
for(int g = 0; g < G; g++){
cnt = visit[gold[g].x][gold[g].y];
if(cnt > 0 && cnt> maxx){
maxx = cnt;
}
}
}
if(Min>maxx && maxx>0){
Min = maxx;
}
}
}
}
if(Min == 1000000) Min = -1;
else Min = Min -1;
cout << "Case #" << tc << endl << Min << endl;
}
return 0;
}
-------------------------------------------------------------------------
#include <iostream>
using namespace std;
int T, N, G, map[20][20], xG, yG, isGold[20][20], ans;
int arr[20][20][4], cnt;
int front, rear, visit[20][20];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
//int maxx, movang2, movangMax, Min = 1000000, ee = -1, ff = -1;
struct Node{
int x, y;
};
Node gold[4];
Node queue[400];
void en(int x, int y){
Node node; node.x = x; node.y = y;
rear++;
queue[rear] = node;
}
Node de(){
return queue[++front];
}
void reset(){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
isGold[i][j] = 0;
visit[i][j] = 0;
for(int k = 0; k < G; k++){
arr[i][j][k] = -1;
}
}
}
}
void resetVisit(){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
visit[i][j] = 0;
}
}
}
void bfs(int x, int y){
en(x, y); visit[x][y] = 1;
while(front != rear){
Node node = de();
for(int k = 0; k < 4; k++){
int r = node.x + dx[k];
int c = node.y + dy[k];
if(r >= 0 && r < N && c >= 0 && c < N && map[r][c] != 0 && visit[r][c] == 0){
en(r, c);
visit[r][c] = visit[node.x][node.y] + 1;
}
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
reset();
cin >> N >> G;
for(int i = 0; i < G; i++){
cin >> xG >> yG;
xG--; yG--;
gold[i].x = xG; gold[i].y = yG;
isGold[xG][yG] = 1;
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> map[i][j];
visit[i][j] = 0;
}
}
int Min = 1000000;
int maxx = 0, movang2 = 0 , movangMax = 0, ee = -1, ff = -1;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(map[i][j] == 1 && isGold[i][j] == 0){
resetVisit();
front = rear = -1;
bfs(i, j);
cnt = 0;
maxx = 0; movang2 = 0;
for(int g = 0; g < G; g++){
cnt = visit[gold[g].x][gold[g].y];
if(cnt > 0){
if(cnt > maxx) maxx = cnt;
arr[i][j][g] =1;
movang2++;
}
}
if(movang2 > movangMax){
movangMax = movang2;
Min = maxx;
ee= i; ff =j;
}
else if(movang2 == movangMax){
if(Min > maxx && maxx > 0){
Min = maxx;
ee= i; ff =j;
}
}
}
}
}
if(Min == 1000000) Min = -1;
else Min = Min -1;
cout << "Case #" << tc << endl << Min << endl;
if(ee != -1 && ff != -1){
for(int i = 0; i < G; i++){
if(arr[ee][ff][i] == -1){
cout << gold[i].x + 1 << " " << gold[i].y + 1 << endl;
}
}
}
}
return 0;
}Editor is loading...
Leave a Comment