Problem Description
I was solving the prob MARIOGAM during these days. I spent plenty of time write and debug and finally got a WA. However, with the help of Internet, I found an AC code. I began to made some self-made data sets to test my program. After 10000 datas' checking, I submitted my program to the OJ. And it still got WA.
I hope to get some help to know where was wrong in my code, or, if somebody could gime me some tricky test data or the data on the OJ.
Sincerely Thanks.
Brief Description of the MARIOGAM
Mario is on a map has five kinds of blocks:
monster, which touch will lose a life,
pipe, which could pass from one place to another,
coin, which hit it will get a coin.
given the start position of mario which has 3 lives, you'll give the expected coin number until game ends.
My program uses Gausian's Method to solve this problem.
My Code
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
#define F(i, j, k) for(int i = j; i <= k; ++i)
typedef long double val_t;
using std::queue;
using std::pair;
using std::cout;
#define mp std::make_pair
int n, m, N, cnt, sx, sy;
const int maxn = 20;
const val_t eps = 1e-7;
const int life = 3;
const int maxm = maxn * maxn * life;
char a[maxn][maxn];
val_t mat[maxm][maxm];
pair<int, int> coin[maxm], out[26];
std::vector<pair<int, int> > in[26];
bool vis[maxn][maxn], vis2[maxn][maxn];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
inline bool ok(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '#');
}
inline int numb(int k, int i, int j) {
int x = n * m;
return (k - 1) * x + (i - 1) * m + j;
}
void pre() {
scanf("%d %d", &n, &m);
N = life * n * m;
F(i, 1, n) {
scanf("%s", a[i] + 1);
F(j, 1, m) {
if(a[i][j] == '$') sx = i, sy = j;
if(a[i][j] >= 'A' && a[i][j] <= 'Z') out[a[i][j] - 'A'] = mp(i, j);
if(a[i][j] >= 'a' && a[i][j] <= 'z') in[a[i][j] - 'a'].push_back(mp(i,j));
if(a[i][j] >= '0' && a[i][j] <= '9') coin[++cnt] = mp(i, j);
}
}
}
bool bfs(int x, int y) {
if(!ok(x,y)) return false;
queue<pair<int, int> > q;
memset(vis2, 0, sizeof(vis2));
vis2[x][y] = 1;
q.push(mp(x,y));
while(!q.empty()) {
int u = q.front().first;
int v = q.front().second;
q.pop();
if(islower(a[u][v])) {
if(!vis2[out[a[u][v] - 'a'].first][out[a[u][v] - 'a'].second]) {
vis2[out[a[u][v] - 'a'].first][out[a[u][v] - 'a'].second] = 1;
q.push(out[a[u][v] - 'a']);
}
continue;
}
if(isdigit(a[u][v])) return true;
F(k, 0, 3) {
int du = u + dx[k];
int dv = v + dy[k];
if(du >= 1 && du <= n && dv >= 1 && dv <= m && a[du][dv] != '#' && !vis2[du][dv]) {
vis2[du][dv] = 1;
q.push(mp(du, dv));
}
}
}
return false;
}
void build_formula() {
F(k, 1, life) F(i, 1, n) F(j, 1, m)
if(!vis[i][j]) {
mat[numb(k, i, j)][numb(k, i, j)] = 1;
} else if(a[i][j] >= 'a' && a[i][j] <= 'z') {
mat[numb(k, i, j)][numb(k, i, j)] = 1;
mat[numb(k, i, j)][numb(k, out[a[i][j] - 'a'].first, out[a[i][j] - 'a'].second)] = -1;
} else {
if(a[i][j] >= '0' && a[i][j] <= '9') mat[numb(k, i, j)][N+1] = -(a[i][j] - '0');
mat[numb(k, i, j)][numb(k, i, j)] = -1;
int p = 0;
F(K, 0, 3) {
int di = i + dx[K];
int dj = j + dy[K];
if(di >= 1 && di <= n && dj >= 1 && dj <= m && a[di][dj] != '#') p++;
}
F(K, 0, 3) {
int di = i + dx[K];
int dj = j + dy[K];
if(di >= 1 && di <= n && dj >= 1 && dj <= m && a[di][dj] != '#'){
if(a[di][dj] != '!')mat[numb(k, i, j)][numb(k, di, dj)] = 1.0 / p;
else if(k != 1) mat[numb(k,i,j)][numb(k-1,di,dj)] = 1.0 / p;
}
}
}
}
void print() {
printf("======================\n");
F(i, 1, N) {
F(j, 1, N) printf("%5.2Lf ", mat[i][j]);
printf("|");
printf("%5.2Lf\n", mat[i][N+1]);
}
printf("======================\n");
}
bool fl[maxm];
val_t gauss() {
F(i, 1, N) {
int r = i;
F(j, i + 1, N) if(fabsl(mat[j][i]) > fabsl(mat[r][i])) r = j;
if(r != i) F(j, 1, N+1) std::swap(mat[r][j], mat[i][j]);
F(j, i + 1, N) if(fabsl(mat[i][i]) > eps){
val_t t = 1.0 * mat[j][i] / mat[i][i];
F(k, 1, N+1) mat[j][k] -= mat[i][k] * t;
}
else fl[i] = 1;
}
for(int i = N; i >= 1; i--) {
for(int j = N; j > i; j--) {
if(mat[i][j] && !fl[j]) mat[i][N+1] -= mat[j][N+1] * mat[i][j];
else if(mat[i][j] && fl[j]) fl[i] = 1;
}
if(fabsl(mat[i][i]) > eps) mat[i][N+1] /= mat[i][i];
else fl[i] = 1;
}
if(fl[numb(life,sx,sy)]) return -1;
return mat[numb(life,sx,sy)][N+1];
}
int main() {
#ifdef orz
freopen("input", "r", stdin);
#endif
pre();
F(i, 1, n) {
F(j, 1, m) {
vis[i][j] = bfs(i, j);
}
}
build_formula();
val_t ans = gauss();
if(ans != -1) printf("%.9Lf\n", ans);
else printf("-1\n");
return 0;
}
AC Code from Internet
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long double real;
const real eps = 1e-12;
const char Empty = '.';
const char Monster = '!';
const char Wall = '#';
const char Mario = '$';
const int maxv = 800;
const int mx[4] = {0, 1, 0, -1};
const int my[4] = {-1, 0, 1, 0};
int extX[27], extY[27];
char map[17][17];
int n, m, sx, sy, tmp;
int isbegin(char s) {
if((s >= 'a') && (s <= 'z')) return s - 'a' + 1;
return 0;
}
int isend(char s) {
if((s >= 'A') && (s <= 'Z')) return s - 'A' + 1;
return 0;
}
int money(char s) {
if((s >= '0') && (s <= '9')) return s - '0';
return 0;
}
void init() {
char s[100];
scanf("%d%d\n", &n, &m);
memset(map, '#', sizeof(map));
int i, j, k;
for(i = 1; i <= n; i++) {
scanf("%s", s);
for(j = 1; j <= m; j++) {
if( (map[i][j] = s[j-1]) == Mario) {
sx = i;
sy = j;
}
if(k = isend(s[j-1])) {
extX[k] = i;
extY[k] = j;
}
}
}
}
int qx[maxv], qy[maxv], ql[maxv];
int isvisit[16][16][3];
int l, r;
int go[maxv][4], gd[maxv], cango[maxv];
vector<int> reach[maxv];
int Queue_Insert(int x, int y, int life) {
if( map[x][y] == Wall ) return 0;
if( map[x][y] == Monster) life--;
if(life < 0) return 0;
if(tmp = isbegin(map[x][y])) {
x = extX[tmp];
y = extY[tmp];
}
if(isvisit[x][y][life] == 0) {
r++;
qx[r] = x;
qy[r] = y;
ql[r] = life;
isvisit[x][y][life] = r;
}
return isvisit[x][y][life];
}
void bfs() {
l = r = 0;
Queue_Insert(sx, sy, 2);
int nx, ny, nl;
int d;
while(l < r) {
l++;
nx = qx[l];
ny = qy[l];
nl = ql[l];
for(d = 0; d < 4; d++) if(map[nx + mx[d]][ny + my[d]] != Wall) {
cango[l]++;
tmp = Queue_Insert(nx + mx[d], ny + my[d], nl);
if(tmp) go[l][gd[l]++] = tmp, reach[tmp].push_back(l);
}
}
}
real mat[maxv][maxv];
real matans[maxv];
real res[maxv];
int Mnum[maxv];
bool solve(int n) {
int i, j, k;
real tmp;
for(i = 1; i <= n; i++) {
j = i;
for(k = i + 1; k <= n; k++) if(fabs(mat[k][i]) > fabs(mat[j][i])) j = k;
if(fabs(mat[j][i]) < eps) return false;
for(k = i; k <= n+1; k++) swap(mat[i][k], mat[j][k]);
for(j = i + 1; j <= n; j++) if(fabs(mat[j][i]) > eps) {
tmp = mat[j][i] / mat[i][i];
for(k = i; k <= n+1; k++) mat[j][k] -= tmp * mat[i][k];
}
}
for(i = n; i; i--) {
matans[i] = -mat[i][n+1];
for(j = i + 1; j <= n; j++) matans[i] -= mat[i][j] * matans[j];
matans[i] /= mat[i][i];
}
return true;
}
bool will[maxv];
void dfs(int x) {
if(will[x]) return;
will[x] = true;
for(int i = 0; i < reach[x].size(); i++) dfs(reach[x][i]);
}
void work() {
int tot, i, j, k, x;
for(i = 1; i <= r; i++) if(money(map[qx[i]][qy[i]])) dfs(i);
for(int ll = 0; ll <= 2; ll++) {
tot = 0;
for(i = 1; i <= r; i++) if((ql[i] == ll) && (will[i])) Mnum[i] = ++tot;
for(i = 1; i <= tot; i++)
for(j = 1; j <= tot+1; j++) mat[i][j] = 0;
k = 0;
for(i = 1; i <= r; i++) if((ql[i] == ll) && (will[i])) {
k++;
mat[k][k] = -cango[i];
mat[k][tot+1] = money(map[qx[i]][qy[i]])* cango[i];
for(j = 0; j < gd[i]; j++) {
x = go[i][j];
if( (ql[x] != ll) || (!will[x])) mat[k][tot+1] += res[x];
else mat[k][Mnum[x]]++;
}
}
if(!solve(tot)) {
printf("-1\n");
return;
}
for(int i = 1; i <= r;i++) if(ql[i] == ll) res[i] = matans[Mnum[i]];
}
cout << res[1] << endl;
}
int main() {
#ifdef orz
freopen("input", "r", stdin);
#endif
cout.setf(ios::fixed);
cout.precision(10);
init();
bfs();
work();
return 0;
}
Data Generator
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstring>
#define random(x) (rand() % x) + 1
int vis[27], color;
int main() {
memset(vis, 0, sizeof(vis));
srand(time(NULL));
int n = 15, m = 15;
color = 2;
int sx = random(n);
int sy = random(m);
printf("%d %d\n", n, m);
for(int i = 1; i <= n; i++) {
for(int j =1; j<=m; j++) {
if(i == sx && j == sy) {
printf("%c",'$');
continue;
}
int k = random(6);
here:
if(k == 1) printf("%c", '#');
if(k == 2) {
int x = random(color);
int cnt = 0;
while(vis[x]) {
x = random(color);
cnt++;
if(cnt > color) {
k = random(6);
goto here;
}
}
vis[x] = 1;
printf("%c", 'A' + x - 1);
}
if(k == 3) {
int x = random(3);
int cnt = 0;
while(!vis[x]){
x = random(color);
cnt++;
if(cnt > color) {
k = random(6);
goto here;
}
}
printf("%c", 'a' + x - 1);
}
if(k == 4) printf("%c", '!');
if(k == 5) printf(".");
if(k == 6) printf("%d", random(9));
}
printf("\n");
}
return 0;
}
Checker
from math import *
import time
import os
n = input()
for i in range(1,int(n)+1):
os.system('./r > input')
if(os.system('./a < input > output.a') != 0):
break
os.system('./b < input > output.b')
f1 = open('output.a', 'r')
f2 = open('output.b', 'r')
x1 = float(f1.readline())
x2 = float(f2.readline())
flag = 0
if(fabs(x1 - x2) > 1e-6):
flag = fabs(x1 - x2)
if flag > 0:
print('Incorrect:{}'.format(flag))
break
else:
print('Correct {}/{}: my answer is {}, his answer is {}'.format(i, n, x1, x2))
#time.sleep(1)
Here is my email:
unrealgengchen AT gmail.com