Untitled
unknown
plain_text
a year ago
7.3 kB
2
Indexable
Input
2
5
1 1 0 0 0
1 2 2 2 1
1 1 2 2 1
2 2 2 1 2
2 2 0 2 0
8
2 0 2 0 2
1 0 1 2 0
0 0 0 2 1
2 0 2 0 1
1 2 1 2 0
0 2 2 0 2
2 1 1 2 2
0 2 1 2 0
Output
Case #1
3
Case #2
4
50
7
2 1 2 2 0
0 2 2 0 0
2 0 2 1 0
0 0 2 1 2
0 2 1 0 2
1 2 1 0 2
1 1 2 0 2
5
0 0 1 0 0
1 2 1 0 2
2 2 0 0 1
2 1 2 1 0
2 1 2 0 2
9
2 2 2 2 2
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 2 2 0
6
2 2 2 2 2
0 0 0 0 0
0 0 2 0 0
2 0 0 0 2
0 0 0 0 0
1 2 2 2 1
10
1 0 1 0 1
2 2 2 2 1
0 2 2 0 2
2 0 2 1 1
2 0 2 2 0
0 2 2 1 1
2 0 2 1 2
2 1 1 2 2
1 1 2 2 2
2 1 0 1 0
9
2 0 1 1 1
0 1 0 1 2
0 1 0 2 2
0 0 0 2 1
2 0 1 0 1
0 0 2 0 2
1 0 0 2 2
2 0 0 1 1
2 0 0 0 0
7
1 2 0 1 0
0 1 2 1 2
2 0 0 0 0
2 2 1 1 2
0 0 2 0 2
0 1 0 1 1
2 1 2 0 2
8
1 2 1 1 2
1 1 2 0 0
2 1 1 2 1
1 2 1 2 0
0 0 2 2 1
1 0 2 0 0
1 2 1 2 0
0 0 2 0 1
12
2 2 2 1 0
1 2 0 0 2
1 0 1 0 1
2 1 2 1 1
1 2 2 1 2
2 2 1 0 1
2 0 1 1 0
0 2 1 0 2
1 2 2 1 2
2 2 1 2 0
1 0 2 0 1
0 0 0 1 0
12
0 0 2 2 0
2 0 0 1 2
0 1 1 2 2
0 0 1 0 2
0 2 2 0 2
1 0 2 2 0
2 2 2 2 1
1 0 1 2 2
2 1 0 1 1
1 0 1 1 0
2 2 1 1 2
0 0 1 0 2
5
1 1 0 0 0
1 2 2 2 1
1 1 2 2 1
2 2 2 1 2
2 2 0 2 0
12
2 1 2 2 2
0 2 2 1 0
0 0 1 0 1
0 1 0 2 0
2 0 0 0 0
0 1 1 0 1
0 1 0 2 2
1 1 0 2 2
2 2 1 2 2
2 0 1 0 2
1 2 1 2 0
2 0 1 1 1
11
1 1 0 0 2
0 1 1 2 2
1 0 0 1 2
2 0 1 1 2
0 0 0 2 0
2 1 2 2 0
2 1 0 2 0
1 1 2 2 1
1 2 0 0 0
2 1 0 0 2
0 0 0 2 1
8
0 0 2 2 2
2 1 1 2 2
2 0 1 1 1
1 1 2 0 0
0 0 2 0 1
0 2 0 0 1
1 1 1 2 0
0 2 0 1 2
9
1 0 0 0 0
2 2 1 1 2
0 1 1 0 0
1 2 0 2 0
1 1 1 0 0
2 1 1 0 1
0 0 1 1 1
2 1 0 0 0
0 1 2 2 1
10
2 2 2 2 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 2 2 0
12
1 0 1 0 1
1 1 1 0 1
0 2 0 2 0
2 0 1 0 0
0 1 2 1 0
1 2 0 1 0
0 1 1 0 2
0 1 1 1 1
0 2 0 1 0
0 0 0 1 2
1 0 0 2 2
0 0 2 0 2
12
0 2 2 0 2
0 2 0 0 0
2 0 1 2 0
0 1 1 2 1
1 2 2 2 0
1 2 1 1 2
2 0 2 1 2
2 1 1 1 0
1 0 0 1 1
2 1 0 1 2
2 1 0 1 1
1 0 2 2 0
9
0 1 1 1 1
1 0 2 0 2
2 2 2 2 1
1 0 0 0 2
1 0 2 2 1
2 1 0 1 2
1 1 0 2 1
2 2 0 0 1
1 1 0 2 0
9
1 1 0 2 0
2 2 0 2 0
1 1 0 1 0
2 0 1 1 0
1 0 1 1 2
0 0 2 1 0
2 0 2 2 1
2 0 1 1 2
2 0 2 0 0
8
2 1 1 1 0
2 1 2 2 1
0 1 0 0 2
0 1 1 0 1
2 0 0 0 2
2 0 1 1 1
0 0 1 1 0
1 1 0 0 0
10
2 0 2 2 2
0 1 0 2 1
0 0 2 1 1
1 0 1 0 1
2 0 0 0 2
0 2 2 0 2
1 1 0 2 2
0 0 1 0 1
1 1 2 0 2
0 1 0 2 0
8
1 2 1 1 1
2 1 2 1 1
1 2 0 2 2
2 0 1 0 0
1 1 2 2 0
1 0 1 2 1
1 2 0 1 2
1 2 0 0 1
10
2 1 0 0 2
2 0 0 0 1
2 1 2 2 0
0 1 0 0 1
0 2 2 2 1
2 1 0 0 0
2 0 2 1 2
2 1 2 1 2
2 0 2 0 2
1 0 2 2 1
8
2 0 2 0 2
1 0 1 2 0
0 0 0 2 1
2 0 2 0 1
1 2 1 2 0
0 2 2 0 2
2 1 1 2 2
0 2 1 2 0
8
1 1 1 2 2
1 1 1 1 2
2 1 2 2 0
2 0 0 2 2
1 0 0 0 2
1 0 2 0 2
2 0 2 0 2
0 2 0 0 1
9
1 2 2 0 2
2 0 2 1 2
1 0 1 2 1
1 0 2 1 1
2 0 1 2 1
1 2 2 0 2
0 2 0 1 0
1 0 2 2 2
2 0 2 0 1
12
1 0 1 2 1
0 2 2 1 0
0 0 2 1 0
1 1 1 1 1
2 0 2 0 0
1 2 1 2 1
0 0 0 1 2
1 1 1 1 0
2 0 2 2 1
0 0 0 2 0
1 0 2 2 2
0 1 1 1 0
8
1 0 0 2 2
2 0 1 1 0
0 0 1 2 2
1 0 1 0 0
1 1 1 0 2
1 0 1 2 0
2 2 0 2 1
0 1 2 1 0
8
2 0 0 0 0
0 0 0 1 0
2 1 0 1 2
1 2 0 0 2
1 2 1 0 1
0 2 1 1 2
1 2 0 2 2
1 1 2 2 0
7
1 0 2 0 1
0 0 1 2 1
2 1 1 2 2
1 0 2 0 1
2 2 1 2 2
0 0 1 0 2
0 0 2 2 0
9
2 2 2 0 1
2 2 0 2 1
1 0 0 2 1
2 2 2 0 1
2 2 0 0 2
1 0 2 1 1
1 2 1 1 2
0 0 2 2 0
2 0 0 0 2
8
1 1 1 0 1
0 1 1 1 2
2 1 1 0 1
2 2 0 0 2
1 1 0 0 2
2 2 0 2 1
2 0 1 1 2
2 0 1 0 0
8
0 2 2 1 1
1 2 1 0 1
0 0 2 2 0
1 0 1 1 1
0 2 0 0 1
0 2 0 1 2
1 0 0 1 1
1 0 2 0 0
12
2 2 2 2 2
2 2 2 1 2
2 1 1 0 0
2 2 2 1 2
2 2 1 0 2
0 0 0 1 1
1 0 0 1 1
0 0 1 1 0
0 1 0 2 1
1 1 1 0 2
0 0 2 1 0
2 0 2 2 2
10
1 0 2 1 2
1 2 1 0 1
1 0 0 1 1
1 1 1 1 1
1 2 1 0 0
1 1 1 2 2
0 1 2 1 1
0 0 0 1 2
1 2 0 1 2
2 1 0 1 0
11
1 0 0 0 2
2 2 0 1 2
1 2 1 0 2
1 1 0 1 0
0 2 1 0 1
2 0 0 1 2
1 0 1 0 2
0 1 1 2 0
1 0 0 0 0
0 2 0 2 1
2 2 0 2 1
9
1 0 1 2 2
2 2 1 1 1
0 0 0 1 0
0 0 0 2 0
2 1 0 1 0
2 0 2 2 1
2 2 1 1 2
1 0 0 1 1
1 1 1 1 2
9
0 0 1 2 2
0 2 0 1 0
2 0 2 2 1
2 2 2 1 1
2 2 2 1 0
0 1 0 2 1
2 1 1 1 1
0 1 0 2 1
2 1 2 2 1
7
0 1 0 1 2
2 0 1 2 1
0 2 2 1 1
1 1 0 0 0
1 0 1 1 1
1 0 2 1 1
2 0 2 0 2
12
0 1 1 0 1
0 2 0 2 2
1 0 0 1 2
2 1 1 1 0
0 2 0 0 1
0 2 1 2 2
2 2 1 1 1
0 1 2 1 0
0 0 1 1 0
2 2 0 1 2
1 1 1 1 2
0 0 1 1 1
10
1 1 2 2 1
2 1 2 2 0
2 2 1 0 0
0 1 2 2 0
1 0 2 0 1
1 2 2 0 2
0 0 0 1 2
1 2 2 1 0
1 0 1 2 2
1 2 1 1 0
11
1 2 0 0 1
2 1 1 0 2
1 2 0 2 2
1 2 0 1 1
2 0 2 2 0
1 2 1 2 1
1 0 0 0 1
0 0 1 1 2
1 0 1 0 2
1 1 2 0 2
2 0 0 2 2
9
0 1 2 2 2
2 2 2 1 1
2 2 1 1 1
1 2 2 2 1
2 1 2 2 2
0 1 2 2 0
0 0 0 0 0
2 1 1 0 1
1 2 2 1 1
11
1 2 1 0 1
0 2 1 1 2
1 0 0 1 1
2 2 0 0 1
1 0 0 2 2
1 2 1 2 0
1 1 0 0 2
2 0 1 2 2
1 2 2 1 1
1 1 1 2 1
2 1 0 0 0
8
1 2 1 2 1
1 1 0 0 2
2 2 2 2 1
1 1 0 0 2
1 2 1 1 2
0 1 1 1 2
0 0 0 1 0
1 2 2 1 0
8
1 0 1 1 1
1 0 2 0 0
2 2 0 1 2
1 0 0 0 2
0 2 0 1 2
2 1 2 0 1
2 2 2 2 0
1 2 2 1 2
8
1 0 2 1 0
0 2 1 0 2
2 0 0 0 1
0 0 2 2 0
1 2 1 0 2
0 1 1 1 1
1 2 1 2 1
2 0 0 1 2
9
1 2 1 0 2
2 2 2 1 1
2 1 1 2 1
1 2 1 0 2
1 2 1 1 0
1 1 1 2 2
0 1 0 2 0
0 0 0 0 0
1 2 0 0 1
8
2 2 0 0 1
2 1 2 2 1
0 0 0 1 1
0 2 1 1 0
0 2 2 1 1
1 0 0 0 2
2 1 2 2 1
#include<iostream>
#define max 1000000
using namespace std;
int queuex[100];
int queuey[100];
int front= -1;
int rear=-1;
int n,m;
int map[25][25];
int visit[25][25];
int d[25][25];
int toado[4][2];
int ans;
int dx[4]={1, -1, 0 ,0};
int dy[4]={0, 0 , 1, -1};
void pushq(int x,int y){
if(rear == max-1) rear =-1;
rear++;
queuex[rear]=x;
queuey[rear]=y;
}
int popx(){
if(front == max-1) front =-1;
front++;
return queuex[front];
}
int popy(){
if(front == max-1) front =-1;
return queuey[front];
}
bool IsEmpty(){
if(front == rear)
return true;
return false;
}
void reset(){
for(int i=0; i < n; i++){
for(int j= 0; j < n; j++){
visit[i][j]=0;
}
}
}
void Try(int i, int j){
int duongdi=0;
int somo=0;
if(somo == m)return;
if(ans > duongdi) ans =duongdi;
pushq(i,j);
visit[i][j] = 1;
d[i][j]=0;
while(!IsEmpty()){
int x1=popx();
int y1=popy();
for(int h=0; h < 4 ; h++){
int i1= x1+dx[h];
int j1 = y1+dy[h];
if(i1 >= 0 && i1 <n && j1>=0 && j1 <n && map[i1][j1] == 1 && visit[i1][j1] == 0){
d[i1][j1] = d[x1][y1] +1;
for(int k =0; k<m; k++){
if(i1 == toado[k][0] && j1 == toado[k][1]){
duongdi += d[i1][j1] ;
somo++;
}
}
pushq(i1,j1);
visit[i1][j1]=1;
}
}
}
}
int main(){
freopen("Text.txt", "r", stdin);
int test;
cin >> test;
for(int tc= 1; tc <= test; tc++){
cin >> n>>m;
for(int i=0; i < m; i++){
for(int j= 0; j < 2; j++){
cin >> toado[i][j];
}
}
for(int i=0; i < n; i++){
for(int j= 0; j < n; j++){
cin >> map[i][j];
}
}
ans =1000000;
for(int i=0; i < n; i++){
for(int j= 0; j < n; j++){
reset();
if(map[i][j] == 1){
Try(i,j);
}
}
}
cout << "Case #" << tc << endl;
cout << ans << endl;
}
return 0;
}
1 1 2 0 0