Bài viết mới

Wednesday, March 23, 2016

Funny code 2 - Bmp picture

Đọc và xử lý file hình ảnh BMP

Tập tin Bitmap Tập tin Bitmap (hay còn gọi là BMP) là một định dạng tập tin dùng để lưu trữ dữ liệu hình ảnh rất phổ biến trên môi trường Windows. Xuất hiện lần đầu tiên trong phiên bản Windows 1.0, định dạng BMP vẫn tồn tại và phát triển cho đến ngày nay. 
Sỡ dĩ có thời gian tồn tại lâu như vậy là do tập tin BMP có cấu trúc rất đơn giản, dữ liệu màu của từng điểm ảnh được lưu trực tiếp, không áp dụng giải thuật nén và bảo toàn được chất lượng ảnh sau khi lưu trữ.

Cấu trúc tập tin Bitmap


Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <stdlib.h>
#define _WIN32_WINNT 0x0500
#include <windows.h>
#include <stdint.h>
const char source[]="E:\\testi.bmp";
const char path[]="E:\\testo.bmp";
#pragma pack(1)

////////////////////////////////////////////////

typedef struct bmp_color
{
    unsigned char R;
    unsigned char G;
    unsigned char B;
} color;
typedef struct bmp_header
{
    char isbmp[2];
    uint32_t sizeof_bmp;
    uint16_t other_1;
    uint16_t other_2;
    uint32_t place_data;
} header;
typedef struct bmp_dib
{
    uint32_t sizeof_dib;
    uint32_t picture_width;
    uint32_t picture_height;
    uint16_t color_layers;
    uint16_t color_deep;
    uint32_t impress_method;
    uint32_t picture_size;
    uint32_t resolution_row;
    uint32_t resolution_column;
    uint32_t colors_used;
    uint32_t main_colors;
    char *thirt_part;
} dib;
typedef struct bmp_data
{
    color **c;
    char padding;
} data;
typedef struct bmp_file
{
    header h;
    dib d;
    data a;
} file;

////////////////////////////////////////////////

file bmp;
color before, after;
FILE *fi=fopen(source,"rb");
FILE *fo=fopen(path,"wb");

////////////////////////////////////////////////

void scan_bmp_file()
{
    if (fi==NULL) return;
    fread(&bmp.h,sizeof(header),1,fi);
    fread(&bmp.d,sizeof(dib),1,fi);
    bmp.a.padding=(4-(bmp.d.picture_size/8)%4)%4;
    bmp.d.thirt_part=new char[bmp.h.place_data-sizeof(header)-sizeof(dib)];
    fread(bmp.d.thirt_part,bmp.h.place_data-sizeof(header)-sizeof(dib),1,fi);
    bmp.a.c = new color*[bmp.d.picture_height];
    for (int i=0; i<bmp.d.picture_height;i++)
    {
        bmp.a.c[i]=new color[bmp.d.picture_width];
        for (int j=0;j<bmp.d.picture_width;j++)
            fread(bmp.a.c[i]+j,sizeof(color),1,fi);
    }
}
void change_bmp_color()
{
    printf("Input color need to chang (RGB): ");
    scanf("%d%d%d",&before.R,&before.G,&before.B);
    printf("Input color to replace (RGB): ");
    scanf("%d%d%d",&after.R,&after.G,&after.B);
    for (int i=0;i<bmp.d.picture_height;i++)
        for (int j=0;j<bmp.d.picture_width;j++)
            if (bmp.a.c[i][j].R==before.R && bmp.a.c[i][j].G==before.G && bmp.a.c[i][j].B==before.B)
            {
                bmp.a.c[i][j].R=after.R;
                bmp.a.c[i][j].G=after.G;
                bmp.a.c[i][j].B=after.B;
            }
}
void print_bmp_console()
{
    HWND console=GetConsoleWindow();
    HDC  hdc=GetDC(console);
    for (int i=bmp.d.picture_height-1;i>=0;i--)
        for (int j=0;j<bmp.d.picture_width;j++)
            SetPixel(hdc,j,bmp.d.picture_height-i-1,RGB(bmp.a.c[i][j].R,bmp.a.c[i][j].G,bmp.a.c[i][j].B));
    ReleaseDC(console, hdc);
}
void print_bmp_file()
{
    if (fo==NULL) return;
    fwrite(&bmp.h,sizeof(header),1,fo);
    fwrite(&bmp.d,sizeof(dib),1,fo);
    fwrite(bmp.d.thirt_part,bmp.h.place_data-sizeof(header)-sizeof(dib),1,fo);
    for (int i=0;i<bmp.d.picture_height;i++)
    {
        for (int j=0;j<bmp.d.picture_width;j++)
            fwrite(bmp.a.c[i]+j,sizeof(color),1,fo);
        for (int j=0;j<bmp.a.padding;j++) fprintf(fo,"0");
    }
}

////////////////////////////////////////////////

int main()
{
    if (fi==NULL || fo==NULL)
    {
        printf("Input error");
        return 0;
    }
    scan_bmp_file();
    change_bmp_color();
    print_bmp_console();
    print_bmp_file();
    fclose(fi);
    fclose(fo);
    return 0;
}


Hình ảnh test:









Vẫn còn update...

Tuesday, March 22, 2016

Thuật toán luồng cực đại trên mạng

Mạng là đồ thị có hướng G = (V, E) trong đó có duy nhất 1 đỉnh A không có cung đi vào và duy nhất 1 đỉnh B không có cung đi ra và mỗi cung của nó có trọng số không âm.
Luồng là phép gán trọng số mỗi cạnh trong mạng bởi 1 số không âm nhỏ hơn trọng số đó và sao cho tổng giá trị nối vào 1 đỉnh bằng tổng giá trị đi ra khỏi đỉnh đó.
Giá trị của 1 luồng là tổng luồng trên các cung đi ra đỉnh phát A ( hoặc thu B).
Luồng cực đại là luồng có giá trị lớn nhất.

Lát cắt, đường tăng luồng, định lý Ford – Fulkerson

Lát cắt (X, Y) là cách phân các tập đỉnh của mạng thành 2 tập X, Y trong đó X chứa đỉnh phát A và Y chứa đỉnh thu B. Khả năng thông qua của lát cắt là tổng trọng số các cạnh (u, v) với u thuộc X và v thuộc Y.
Định lý Ford-Fulkerson: Lát cắt nhỏ nhất (hẹp nhất) chính là giá trị của luồng cực đại.
Thuật toán: với f là một luồng trong mạng G(V, E).
  1. Xây dựng đồ thị tăng luồng Gf(V, Ef):
  • Nếu f[u, v] < c[u, v] thì thêm (u, v) vào Ef với trọng số c[u, v] – f[u, v] (cung thuận) chỉ khả năng tăng luồng trên cung (u, v).
  • Nếu f[u, v] > 0 thì thêm cung (v, u) vào Ef với trọng số f[u, v] (cung nghịch) chỉ khả năng giảm luồng trên cung (u, v).
    2.   Tìm đường đi cơ bản từ A  B trên đồ thị Gf. Gọi Delta là giá trị nhỏ nhất trên đường đi và đặt
  • f[u, v] = f[u, v] + Delta nếu (u, v) nằm trên đường đi và là cung thuận.
  • f[u, v] = f[u, v] - Delta nếu (u, v) nằm trên đường đi và là cung nghịch. 
Khi đó giá trị luồng f tăng Delta so với luồng cũ và đường đi tìm được gọi là đường tăng luồng
Tiến hành thực hiện đường tăng luồng cho đến khi không tăng được nữa. Đồ thị f kết quả chính là luồng cực đại cần tìm.

Vậy các bước cụ thể tìm luồng cực đại trên mạng:
  • Khởi tạo luồng 0
  • Tìm đường đi cơ bản từ A  B trên đồ thị tăng luồng (đường tăng luồng), cập nhật lại kết quả f và Gf, lặp lại bước này cho đến khi không tìm được nữa.
  • Xuất kết quả luồng cực đại tìm được.
Code luồng cực đại dùng định lý Ford - Fulkerson:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#define ma 1002
long long n,m,s,t,a[ma][ma]={0},max_flow=0,trace[ma][2],current[ma][ma]={0};
void scan_input()
{
    long long i,u,v,c;
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for (i=0;i<m;i++)
    {
        scanf("%lld%lld%lld",&u,&v,&c);
        a[u][v]+=c;
    }
}
long long mi(long long value1, long long value2)
{
    return value1>value2?value2:value1;
}
bool find_path()
{
    long long free[ma],que[ma],i,fron=-1,rear=0;
    for (i=1;i<=n;i++) free[i]=0;
    que[rear]=s;
    trace[s][1]=ma;
    free[s]=1;
    while (fron<rear)
    {
        fron++;
        for (i=1;i<=n;i++)
            if (free[i]==0 && (a[que[fron]][i]>0 || current[i][que[fron]]>0))
            {
                rear++;
                que[rear]=i;
                free[i]=1;
                trace[i][0]=que[fron];
                if (a[que[fron]][i]==0) trace[i][0]=-trace[i][0];
                if (a[que[fron]][i]>0) trace[i][1]=mi(a[que[fron]][i],trace[que[fron]][1]);
                else trace[i][1]=mi(current[i][que[fron]],trace[que[fron]][1]);
                if (i==t) return true;
            }
    }
    return false;
}
void increase_flow()
{
    long long i=t,min_value=trace[i][1];
    while (i!=s)
    {
        if (trace[i][0]>0)
        {
            a[trace[i][0]][i]-=min_value;
            current[trace[i][0]][i]+=min_value;
        }
        else
        {
            a[i][-trace[i][0]]+=min_value;
            current[i][-trace[i][0]]-=min_value;
        }
        i=trace[i][0]>0?trace[i][0]:-trace[i][0];
    }
}
void print_result()
{
    long long i;
    for (i=1;i<=n;i++)
        if (current[s][i]>0) max_flow+=current[s][i];
    printf("%lld",max_flow);
}
int main()
{
    scan_input();
    while (find_path()) increase_flow();
    print_result();
    return 0;
}

Tham khảo: >> Giải thuật và lập trình - Trang 257
                     >> Competitive programming 3 - Trang 163
Bài tập:
1.   UVa 00259 - Software Allocation              Code(Submitted 16-06-2017)
2.   UVa 00820 - Internet Bandwidth               Code(Submitted 17-06-2017)
3.   UVa 10092 - The Problem with the ...        Code(Submitted 17-06-2017)
4.   UVa 10511 - Councilling                            Code(Submitted 27-06-2017)
5.   UVa 10779 - Collectors Problem               Code(Submitted 28-06-2017)
6.   UVa 11045 - My T-Shirt Suits Me
7.   UVa 11167 - Monkeys in the Emei ...
8.   UVa 11418 - Clever Naming Patterns
9.   UVa 10330 - Power Transmission 

10. UVa 10480 - Sabotage 
11. UVa 11380 - Down Went The Titanic 
12. UVa 11506 - Angry Programmer 
13. UVa 12125 - March of the Penguins

Funny code 1 - Copy file

Code C/C++ thực hiện copy file có định dạng bất kì từ một địa chỉ sang địa chỉ khác


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <time.h>
const char source[]="E:\\test_inputfile.exe";
const char path[]="D:\\test_outputfile.exe";
#define oneread 10000000
char s[oneread];
long long value=0,cou,current=0,time_begin,i;
int main()
{
    FILE *f=fopen(source,"rb");
    FILE *f1=fopen(path,"wb");
    while ((cou=fread(s,1,oneread,f))!=0) value+=cou;
    fseek(f,0,0L);
    if (f==NULL || f1==NULL)
    {
        if (f==NULL) printf("Source file not found!!");
        if (f1==NULL) printf("Path directory not correct!!");
        return 0;
    }
    system("color 2");
    while ((cou=fread(s,1,oneread,f))!=0)
    {
        time_begin=clock();
        fwrite(s,1,cou,f1);
        current+=cou;
        system("cls");
        printf("Size of file: %.2f MB\n",value/1024.0/1024);
        for (i=1;i<=100*(value-current)/value;i++) printf("|");
        if (100*(value-current)/value==0) printf("\nComplete\n");
        else printf("\nCopying... %I64d%% remain\n",100*(value-current)/value);
        printf("Speed %.2f MB/s",cou/((clock()-time_begin)/1000.0)/1024/1024);
    }
    fclose(f);
    fclose(f1);
    return 0;
}