P141PROB spoj PTIT - Tuần lễ công dân

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P141PROB/

1. Đề bài P141PROB spoj

Sau khi đi nhập học, Tèo rất phấn khởi và bắt đầu ngay việc học ở trường đại học. Tuần học đầu tiên là tuần lễ công dân. Mục tiêu chính của Tèo cũng như các tân sinh viên khác là kết bạn.

Hội trường gồm có R*C vị trí chỗ ngồi (R hàng và C cột). Mỗi bạn sinh viên sẽ cố gắng làm quen và bắt tay với tất cả những người bạn xung quanh mình. Như vậy, mỗi bạn sẽ làm quen được tối đa là 8 người bạn mới.

Buổi học đã bắt đầu, nhưng không may, Tèo lại đến muộn (là người muộn nhất). Tèo sẽ chọn một vị trí trống sao cho có thể làm quen với nhiều bạn mới nhất có thể. Nếu không có ghế trống nào, Tèo quyết định bùng học. 😀

Hãy tính toán số lượng cái bắt tay sẽ được thực hiện trong buổi học đầu tiên này.

Input

Dòng đầu tiên là 2 số nguyên R và C (1 <= R, C <= 50).

R dòng tiếp theo, mỗi dòng chứa C kí tự. Kí tự ‘.’ thể hiện chỗ ngồi còn trống, và kí tự ‘o’ thể hiện một sinh viên.

Output

In ra một số nguyên duy nhất là số lượng cái bắt tay sẽ được thực hiện.

Example

Test 1:

Input:

2 3
..o
o..

Output:

Giải thích test 1: Tèo có thể ngồi ở vị trí (1,2) hoặc (2,1). Khi đó có tất cả 2 cái bắt tay được thực hiện.

Test 2:

Input:

2 2
oo
oo

Output:

Giải thích test 2: Không có ghế trống nào nên Tèo quyết định đi về. Tuy nhiên, tại buổi học đó vẫn có

tổng cộng 6 cái bắt tay được diễn ra.

2. Hướng dẫn giải P141PROB spoj PTIT

– Đầu tiên bạn sẽ tìm vị trí bắt tay được nhiều nhất cho Tèo. Đánh dấu vị trí đó xem như là 1 chỗ ngồi.

– Thực hiện duyệt đếm số bắt tay có thể.

Lưu ý: A[i,j] bắt tay với A[u,v] <=> A[u,v] bắt tay A[i,j] Nên bạn chỉ tính một lần. có thể dùng mảng đánh dấu để xử lí trường hợp này.

3. Code tham khảo P141PROB spoj PTIT

const   fi='';
        nmax=51;
type    data=longint;
var
        f:text;
        A,B:array[0..nmax,0..nmax] of char;
        m,n:data;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,m,n);
        fillchar(a,sizeof(a),'.');
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                read(f,a[i,j]);
                        readln(f);
                end;
        close(f);
        B:=a;
end;

function tinh(x,y:data):data;
var     i,j:data;
begin
        tinh:=0;
        for i:=x-1 to x+1 do
                for j:=y-1 to y+1 do
                        if a[i,j]='o' then
                                inc(tinh);
end;


procedure xuli;
var     i,j,resmax,k,u,v:data;
        res:int64;
begin
        res:=0;
        resmax:=0;
        for i:=1 to m do
                for j:=1 to n do
                        if a[i,j]='.' then
                                begin
                                        k:=tinh(i,j);
                                        if k>resmax then
                                                begin
                                                        resmax:=k;
                                                        u:=i;
                                                        v:=j;
                                                end;
                                end;
        if resmax<>0 then
                a[u,v]:='o';
        for i:=1 to m do
                for j:=1 to n do
                        begin
                                if a[i,j]='o' then
                                        begin
                                                a[i,j]:='.';
                                                res:=res+tinh(i,j);
                                        end;
                        end;

        writeln(res);
end;

begin
        docfile;
        xuli;
end.

P141PROB spoj PTIT – Tuần lễ công dân