NKTABLE

11953. NKTable

Mã bài: NKTABLE

Cho bảng m*n ô, mỗi ô có 1 trong 3 số: 0, 1, 2:

0, 1: ô được phép đi vào.

2: ô cấm, không được đi vào.

            Yêu cầu: Xuất phát từ ô (1; 1), chỉ dùng các phép di chuyển sang phải hoặc xuống dưới ô kề cạnh, hãy di chuyển đến ô (m; n) sao cho dãy nhị phân tạo thành từ các ô trên đường đi là số lớn nhất có thể (trong hệ thập phân).

            Dữ liệu đảm bảo luôn tìm được đường đi.

            Giới hạn:       2 <= m, n <= 500

            Input:

-         Dòng đầu tiên gồm 2 số m,  n.

-         m dòng tiếp theo, mỗi dòng gồm n số thuộc tập {0; 1; 2}. Số thứ j ở dòng i biểu diễn ô (i;j) trên bảng.

-         Các số cùng dòng trong input cách nhau một hoặc nhiều dấu cách.

            Output:

-         Một dòng duy nhất là chuỗi nhị phân có giá trị số ở hệ thập phân lớn nhất tìm được (các số in liền).

Ví dụ:

Input:	Output:
3 5                                                                                                                                                                                                                            0 1 2 0 2 0 1 0 0 1 1 2 1 2 1	0110011

Solution:
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;

int M,N;
string s[501][501];
int a[501][501];
string oo;
int main()
{
oo=string("00");
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);
cin >> M >> N;
for(int i=1;i<=M;i++)
for(int j=1;j<=N;j++)
scanf("%d",&a[i][j]);


// cout << s[1][1];
/*
s[1][2]=string("01001");
s[1][3]=string("0010");
cout << "s12=" << s[1][2]<<endl;
cout << "s13=" << s[1][3]<<endl;
if(s[1][2]<s[1][3])
printf("Nho");
else
printf("Khong nho");
*/
string temp;
s[1][1]=a[1][1]+'0';
// cout << s[1][1];
for(int j=2;j<=N;j++)
if(a[1][j-1]!=2&&a[1][j]!=2)
{
temp=(a[1][j]+'0');
s[1][j]=s[1][j-1]+temp;
}
else
s[1][j]=oo;

for(int i=2;i<=M;i++)
if(a[i-1][1]!=2&&a[i][1]!=2)
{
temp =(a[i][1]+'0');
s[i][1]=s[i-1][1]+temp;
}
else
s[i][1]=oo;

for(int i=2;i<=M;i++)
for(int j=2;j<=N;j++)
{
temp=a[i][j]+'0';
if(a[i][j]==2)
s[i][j]=oo;
else
s[i][j]=max(s[i-1][j],s[i][j-1])+temp;
}

/*
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
cout << s[i][j] << ", ";
cout << endl;
}
*/
cout << s[M][N];
return 0;
}

bool operator<(string ss,string tt)
{
return ss<tt;
}